Count integer pairs satisfying 1/x + 1/y = 1/N
MicrosoftSoftware Engineer · Online AssessmentLast updated
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 \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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.