Counting GCD Pairs in a Range

A single line containing three space-separated integers: L, R, and G.

Print a single integer representing the total count of valid pairs (x, y).

A crucial insight is that if GCD(x, y) = G, then both x and y must be multiples of G. Let x = G * a and y = G * b.

Sample Input 1:

1 11 5

Sample Output 1:

3

Explanation for Sample 1:

We need pairs `(x, y)` where `1 <= x, y <= 11` and `GCD(x, y) = 5`.
The possible multiples of 5 in this range are `{5, 10}`.
The pairs we can form from this set are `(5, 5)`, `(5, 10)`, `(10, 5)`, `(10, 10)`.
- `GCD(5, 5) = 5`. Valid.
- `GCD(5, 10) = 5`. Valid.
- `GCD(10, 5) = 5`. Valid.
- `GCD(10, 10) = 10`. Invalid.
There are 3 valid pairs.

Sample Input 2:

1 10 7

Sample Output 2:

1

Explanation for Sample 2:

We need pairs `(x, y)` where `1 <= x, y <= 10` and `GCD(x, y) = 7`.
The only multiple of 7 in this range is `{7}`.
The only possible pair is `(7, 7)`.
`GCD(7, 7) = 7`. This is a valid pair.
The total count is 1.

Expected Time Complexity:

The expected time complexity is O((R/G)^2 * log(R/G)).

Constraints:

1 <= L <= R <= 1000
1 <= G <= 1000

Time limit: 1 sec