Count integer pairs satisfying 1/x + 1/y = 1/N

You are given a positive integer N ($1 \le N \le 10^6$). Consider the Diophantine equation:

$\frac{1}{x} + \frac{1}{y} = \frac{1}{N},$

where x and y are positive integers.

Determine how many ordered pairs of positive integers (x, y) satisfy this equation.

Formally, count the number of pairs (x, y) with x > 0, y > 0, and

$\frac{1}{x} + \frac{1}{y} = \frac{1}{N}.$

Output this count for the given N.

Your algorithm should be efficient enough to handle values up to N = 10^6.

Count integer pairs satisfying 1/x + 1/y = 1/N

You are given a positive integer N (1 <= N <= 10^6). Count how many ordered pairs of positive integers (x, y) satisfy the equation:

1/x + 1/y = 1/N

with x > 0 and y > 0.

Examples

• N = 1: the only solution is (2, 2), so the answer is 1.
• N = 2: the ordered pairs are (3, 6), (4, 4), (6, 3), so the answer is 3.
• N = 4: the answer is 5.

Hint on the math: Rewrite the equation. Multiplying through and rearranging, with x = N + a and y = N + b, the condition becomes ab = N^2 for positive integers a, b. Each ordered factorization of N^2 gives exactly one ordered pair (x, y). Therefore the answer equals the number of positive divisors of N^2. If N = p1^e1 * p2^e2 * ... then N^2 = p1^(2e1) * ..., and the divisor count is the product of (2*ei + 1) over all prime factors.

Return the count.

Constraints

• 1 <= N <= 10^6
• x and y are positive integers
• Count ordered pairs: (x, y) and (y, x) are counted separately when x != y

Hints

1. Manipulate 1/x + 1/y = 1/N algebraically. With x = N + a and y = N + b, the equation reduces to a*b = N^2.
2. Every positive divisor a of N^2 yields exactly one valid ordered pair, so the answer is the number of positive divisors of N^2.
3. If N = product of p_i^e_i, then N^2 = product of p_i^(2e_i), and the divisor count is the product of (2e_i + 1). Factor N by trial division up to sqrt(N).