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.