Katkat

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

MicrosoftSoftware Engineer · Online Assessment

Last 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.