최대공약수가 정해진 순서쌍의 개수
시간 제한2초메모리 제한128 MB
x <= a, y <= b이고 gcd(x, y) = d를 만족하는 순서쌍 (x, y)의 개수를 최대 5만 개의 질의에 대해 구하는 문제입니다.
문제
세 정수 a, b, d가 주어진다. 다음 조건을 모두 만족하는 자연수 순서쌍 (x, y)의 개수를 구하라.
- 1 <= x <= a
- 1 <= y <= b
- gcd(x, y) = d
입력
하나의 입력 파일에 여러 질의가 주어진다. 첫째 줄에는 질의의 개수 N이 주어진다. 이어지는 N개의 줄에는 각 질의를 나타내는 세 정수 a, b, d가 주어진다.
출력
각 질의의 답을 한 줄에 하나씩 출력한다.
제한
- 1 <= N <= 50,000
- 1 <= a, b, d <= 50,000
- d <= a
- d <= b
힌트
공개 테스트의 첫 번째 질의에서는 (2, 2), (2, 4), (4, 2) 세 개의 순서쌍이 있다. 두 번째 질의에서는 (3, 3), (6, 3) 두 개의 순서쌍이 있다.