Author: SQU_Test
DIFFICULTY:
Medium
PREREQUISITES:
Greatest Common Divisor (GCD), Lowest Common Multiplier (LCM).
PROBLEM:
A pair of integers (a, b) is defined to be good, if GCD(a, b) = x and LCM(a, b) = y, where GCD(a, b) denotes the greatest common divisor of a and b, and LCM(a, b) denotes the least common multiple of a and b.
You are given two integers x and y. You are to find the number of good pairs of integers (a, b) such that l ≤ a, b ≤ r. Note that pairs (a, b) and (b, a) are considered different if a ≠ b.
EXPLANATION:
Let’s consider some suitable pair (a, b). As GCD(a, b) = x, we can present number a as c . x, and number b as d . x, where we know that c, d >= 1 and GCD(c, d) = 1.
Let’s consider too that from the restriction from the problem l ≤ a, b ≤ r we surely know the restriction for c and d, that is 1/x ≤ c, d ≤ r/x.
Let’s remember we know that x . y = a . b (because x is GCD(a, b), y is LCM(a, b)). Then we can get x . y = c . x . d . x. Dividing by x:
y = c . d. x.
y/x = c . d.
Now if mod(y, x) ≠ 0, answer equals 0.
Else as y/x is surely less than 10^9, we can just sort out all possible pairs (c, d) of divisors y/x, such that c . d = y/x, and then to check that GCD(c, d) = 1 and c, d are in the getting above restrictions. Complexity of this solution is O(y^{0.5}).
TIME COMPLEXITY:
Time complexity of the solution is O((y^{0.5}) as explained above.
SOLUTIONS:
Setter’s Solution (C++)
#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b) {
int t = a % b;
a = b;
b = t;
}
return a;
}
int main() {
int l, r, x, y;
cin >> l >> r >> x >> y;
if (y % x != 0){
cout << 0 << '\n';
return 0;
}
int ans = 0;
int n = y / x;
for (int d = 1; d * d <= n; ++d) {
if (n % d == 0) {
int c = n / d;
if (l <= c * x && c * x <= r && l <= d * x && d * x <= r && gcd(c, d) == 1) {
if (d * d == n) ++ans;
else ans += 2;
}
}
}
cout << ans << '\n';
return 0;
}
Setter’s Solution (Python)
def GCD(a,b):
return a if b == 0 else GCD(b, a%b)
l,r,x,y = map(int,input().split())
tmp = x * y
ans = 0
for i , j in zip(range(x,r+1,x) , range(100000)):
if i < l:
continue
if tmp % i != 0:
continue
t = tmp // i
if i > t:
continue
if t > r:
continue
if GCD(t,i) != x:
continue
ans += 1
if t != i:
ans += 1
print(ans)