Editorial for HHPC1 P4 - Yet Another A+B Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: dxke01

The answer for some c is equal to d(c^2) where d is the divisor function.

Proof Rearrange the equation as follows:
\frac{1}{x} + \frac{1}{y} = \frac{1}{c}
\frac{x+y}{xy} = \frac{1}{c}
xy = cx + cy
-cx - cy + xy = 0
Using Simon's Favourite Factoring Trick:
(x - c)(y - c) = c^2
From here its obvious the answer is just the number of factors of c^2

Time Complexity: \mathcal{O}(T * \sqrt{C})


There are no comments at the moment.