Pairs with Given GCD and LCM

Problem Overview

If gcd is x and lcm is y, then a*b = x*y and both a and b are multiples of x.

Intuition

If gcd is x and lcm is y, then a*b = x*y and both a and b are multiples of x. Write a = x*v and b = x*w. Then v*w = y/x and gcd(v, w) must be 1. Counting ordered pairs (a, b) becomes counting ordered coprime factor pairs of n = y/x.

Algorithm

1If y is not divisible by x, return 0.
2Set n = y / x.
3For each factor i up to sqrt(n), let j = n / i.
4If gcd(i, j) is 1, add 2 for the ordered pair, or 1 when i equals j.
5Return the total.

Example Walkthrough

Input: x = 2, y = 12

1. n = 6. Coprime factor pairs are (1,6) and (2,3).
2. They map to (2,12), (12,2), (4,6), and (6,4).
3. Total ordered pairs: 4.

Output: 4

Common Pitfalls

• LCM must be a multiple of GCD; otherwise the answer is 0.
• Count ordered pairs, so (a, b) and (b, a) both count when a differs from b.
• Only keep factor pairs that are coprime.
• Avoid scanning all values up to y; work on factors of y/x only.

Pairs with Given GCD and LCM.java

Java

// Approach: Need a*b = x*y and gcd(a,b)=x. Write a=x*v, b=x*w with
// gcd(v,w)=1 and v*w = y/x. Count ordered coprime factor pairs of n=y/x
// (or equivalently 2^omega(n) distinct-prime assignments).
// Complexity: O(sqrt(y/x)) time and O(1) extra space.
class Solution {

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public int pairCount(int x, int y) {
        if (y % x != 0) {
            return 0;
        }

        int n = y / x;
        int ans = 0;

        for (int i = 1; (long) i * i <= n; i++) {
            if (n % i != 0) {
                continue;
            }
            int j = n / i;
            if (gcd(i, j) == 1) {
                ans += (i == j) ? 1 : 2;
            }
        }

        return ans;
    }
}

Was this solution helpful?