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

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

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Overview

Comments (0)