HW3C - Editorial

PROBLEM LINK:
Practice
Source

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)