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:

4

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:

  1. Put the prime factor in p.

  2. 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:

3

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.