Last Updated: 24 Sep, 2025
Counting GCD Pairs in a Range
Easy
Asked in company
You are given three positive integers: L, R, and G.
Your task is to count the number of ordered pairs (x, y) that satisfy two conditions:
1) Both x and y must be within the inclusive range [L, R].
2) The Greatest Common Divisor (GCD) of x and y must be exactly G.
Input Format:
A single line containing three space-separated integers: L, R, and G.
Output Format:
Print a single integer representing the total count of valid pairs (x, y).
Note:
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.
