Count integer pairs satisfying 1/x + 1/y = 1/N
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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`.
Quick Answer: This question evaluates understanding of number theory and algorithmic problem-solving, focusing on Diophantine equation manipulation, divisor counting, and translating algebraic constraints into combinatorial counts.
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 a*b = 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^(2*e1) * ..., 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
Examples
Input: (1,)
Expected Output: 1
Explanation: N=1: only pair is (2,2). N^2=1 has 1 divisor.
Input: (2,)
Expected Output: 3
Explanation: N=2: pairs (3,6),(4,4),(6,3). N^2=4 has divisors 1,2,4 -> 3.
Hints
- Manipulate 1/x + 1/y = 1/N algebraically. With x = N + a and y = N + b, the equation reduces to a*b = N^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.
- If N = product of p_i^e_i, then N^2 = product of p_i^(2*e_i), and the divisor count is the product of (2*e_i + 1). Factor N by trial division up to sqrt(N).