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$ ~c~ is equal to $d(c^2)$ ~d(c^2)~ where $d$ ~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})$ ~\mathcal{O}(T * \sqrt{C})~

Comments

There are no comments at the moment.