Count Ordered Pairs with Given GCD and LCM in Java Using Prime Factorization

Problem Statement

Given two positive integers x and y, representing the GCD and LCM of two unknown positive integers a and b, find the number of valid ordered pairs (a, b).
The pair (a, b) and (b, a) are considered different when a != b.

Example

Input:

x = 2
y = 12

Output:

The valid pairs are:

(2, 12)
(4, 6)
(6, 4)
(12, 2)

All these pairs have:

GCD = 2
LCM = 12

Approach

We use the important mathematical property:

a × b = GCD(a, b) × LCM(a, b)

Since:

GCD(a, b) = x
LCM(a, b) = y

we get:

a × b = x × y

Because the GCD of a and b is x, we can write:

a = x × p
b = x × q

where p and q are coprime.

Substituting into the product equation:

(x × p) × (x × q) = x × y

After simplifying:

p × q = y / x

Therefore, the first thing we need to check is whether y is divisible by x.

If:

y % x != 0

then no valid pair exists.

Counting the Pairs

Let:

n = y / x

We need to divide the prime factors of n between p and q.

For every distinct prime factor, there are two choices:

Put the prime factor in p.
Put the prime factor in q.

If n has k distinct prime factors, the number of ordered pairs is:

2^k

Example

For:

x = 2
y = 12

we get:

n = 12 / 2
  = 6

Prime factorization:

6 = 2 × 3

There are two distinct prime factors: 2 and 3.

Therefore:

answer = 2^2
       = 4

The four possibilities correspond to:

p = 1, q = 6  → (a, b) = (2, 12)
p = 2, q = 3  → (a, b) = (4, 6)
p = 3, q = 2  → (a, b) = (6, 4)
p = 6, q = 1  → (a, b) = (12, 2)

Java Code

class Solution {
    public int pairCount(int x, int y) {

        // LCM must be divisible by GCD
        if (y % x != 0) {
            return 0;
        }

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

        // Find distinct prime factors of n
        for (int i = 2; i * i <= n; i++) {

            if (n % i == 0) {
                distinctPrimeFactors++;

                // Remove all occurrences of this prime factor
                while (n % i == 0) {
                    n /= i;
                }
            }
        }

        // If one prime factor remains
        if (n > 1) {
            distinctPrimeFactors++;
        }

        // Number of ordered pairs = 2^k
        return 1 << distinctPrimeFactors;
    }
}

Code Explanation

1. Check Whether LCM Is Divisible by GCD

if (y % x != 0) {
    return 0;
}

The LCM of two numbers is always divisible by their GCD.

For example:

GCD = 2
LCM = 12

is valid because:

12 % 2 = 0

But:

GCD = 6
LCM = 4

is impossible because:

4 % 6 != 0

2. Calculate `y / x`

int n = y / x;

This gives the number whose distinct prime factors we need to count.

For:

x = 2
y = 12

we get:

n = 6

3. Find Distinct Prime Factors

for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        distinctPrimeFactors++;

        while (n % i == 0) {
            n /= i;
        }
    }
}

The for loop checks possible factors from 2 to √n.

When a factor is found, we increase the count:

distinctPrimeFactors++;

Then we remove all occurrences of that prime:

while (n % i == 0) {
    n /= i;
}

This is important because we only need the number of distinct prime factors.

For example:

n = 12
12 = 2 × 2 × 3

There are only two distinct prime factors:

2 and 3

not three.

4. Handle the Remaining Prime Factor

if (n > 1) {
    distinctPrimeFactors++;
}

After checking factors up to √n, if n is still greater than 1, then n itself is a prime factor.

For example:

n = 15

We find:

and after removing it:

n = 5

Since 5 > 1, it is another distinct prime factor.

5. Calculate `2^k`

return 1 << distinctPrimeFactors;

The left-shift operation is equivalent to:

2^distinctPrimeFactors

For example:

k = 0 → 1
k = 1 → 2
k = 2 → 4
k = 3 → 8

So if n has 2 distinct prime factors, the answer is:

2² = 4

Another Example

Consider:

x = 6
y = 30

First:

n = y / x
  = 30 / 6
  = 5

5 has one distinct prime factor.

Therefore:

answer = 2¹ = 2

The pairs are:

(6, 30)
(30, 6)

Example with More Prime Factors

Consider:

x = 1
y = 30

Then:

n = 30

Prime factorization:

30 = 2 × 3 × 5

There are 3 distinct prime factors.

Therefore:

answer = 2³
       = 8

The ordered pairs are:

(1, 30)
(2, 15)
(3, 10)
(5, 6)
(6, 5)
(10, 3)
(15, 2)
(30, 1)

Complexity Analysis

Let:

n = y / x

We factorize n by checking up to √n.

Time Complexity:

O(√n)

which is:

O(√(y / x))

Space Complexity:

O(1)

because we use only a few integer variables.

Key Takeaway

The main mathematical observation is:

a = x × p
b = x × q

where:

gcd(p, q) = 1

and:

p × q = y / x

Every distinct prime factor of y / x can independently belong to either p or q.

Therefore, if there are k distinct prime factors:

Number of ordered pairs = 2^k

This allows us to solve the problem efficiently using prime factorization instead of generating all possible pairs.

Problem Statement

Example

Approach

Counting the Pairs

Example

Java Code

Code Explanation

1. Check Whether LCM Is Divisible by GCD

2. Calculate y / x

3. Find Distinct Prime Factors

4. Handle the Remaining Prime Factor

5. Calculate 2^k

Another Example

Example with More Prime Factors

Complexity Analysis

Key Takeaway

2. Calculate `y / x`

5. Calculate `2^k`