Description

Given two positive integers x0 and y0 (2 ≤ x0 < 100000, 2 ≤ y0 ≤ 1000000), find the number of pairs of positive integers (P, Q) that satisfy the following conditions:

1. P and Q are positive integers.
2. The greatest common divisor (GCD) of P and Q is x0, and the least common multiple (LCM) of P and Q is y0.

Input Format

A single line containing two positive integers x0 and y0.

Output Format

A single line containing the number of valid pairs (P, Q) that satisfy the given conditions.

Example

Input

3 60

Output

4

Explanation

The valid pairs (P, Q) are:

• (3, 60)
• (12, 15)
• (15, 12)
• (60, 3)

Thus, there are 4 valid pairs.

Solution Approach

1. Key Insight: For any two numbers P and Q, the product of their GCD and LCM equals the product of the numbers themselves, i.e., GCD(P, Q) * LCM(P, Q) = P * Q. Given GCD(P, Q) = x0 and LCM(P, Q) = y0, we have P * Q = x0 * y0.
2. Variable Substitution: Let P = x0 * a and Q = x0 * b, where a and b are coprime (i.e., GCD(a, b) = 1). Then, LCM(P, Q) = x0 * a * b = y0, which implies a * b = y0 / x0. Therefore, y0 must be divisible by x0; otherwise, there are no solutions.
3. Factorization: The problem reduces to finding the number of coprime pairs (a, b) such that a * b = y0 / x0. This involves factorizing the number y0 / x0 into its prime factors and then using combinatorial principles to count the coprime pairs.

Solution Code

import math

x0, y0 = map(int, input().split())

if y0 % x0 != 0:
    print(0)
else:
    k = y0 // x0
    if k == 1:
        print(1)
    else:
        # Factorize k into its prime factors
        factors = {}
        temp = k
        for i in range(2, int(math.isqrt(temp)) + 1):
            if temp % i == 0:
                count = 0
                while temp % i == 0:
                    temp = temp // i
                    count += 1
                factors[i] = count
        if temp > 1:
            factors[temp] = 1
        
        # The number of coprime pairs (a, b) is 2^m, where m is the number of distinct prime factors
        m = len(factors)
        print(2 ** m)

Explanation

1. Check Divisibility: The code first checks if y0 is divisible by x0. If not, there are no valid pairs, and the output is 0.
2. Factorization: If y0 is divisible by x0, the code computes k = y0 / x0 and factorizes k into its prime factors.
3. Count Coprime Pairs: The number of coprime pairs (a, b) such that a * b = k is given by 2 raised to the power of the number of distinct prime factors of k. This is because for each distinct prime factor, there are two choices: either it entirely belongs to a or entirely to b.
4. Output Result: The result is printed as 2^m, where m is the number of distinct prime factors of k.

This approach efficiently narrows down the problem to prime factorization and combinatorial counting, providing an optimal solution.

3 60

4

Hint

There are 4 possible pairs for (P, Q): (3, 60), (15, 12), (12, 15), (60, 3).

For 100% of the data, 2 ≤ x₀, y₀ ≤ 10^5.

Source

NOIP2001-J2