EQUATIO - Editorial






Let d = gcd(x,y), x = dp, y = dq. It’s a well-known thing that lcm(x,y) gcd(x,y) = xy*, so the given equation can be written as d2pq = a + bdpq + cd ( * ). From this equation we get pq = (a / d + c) / (d - b) ( ** ).

As all summands except a in ( * ) are divisible by d, a should obviously be divisible by d too. Therefore, if a > 0, we already have at most 240 possible values of d (240 is the maximum number of divisors of an integer not exceeding 106). If a = 0, then from (* * ) it can be seen that c should be divisible by d - b, so there are again at most 240 possible values of d. If both a and c are 0, there are two cases – the answer is 0 for b = 0 and -1 for b > 0.

Let’s fix a particular value of d. From ( * * ) we can find t = pq. That means that we should add the number of ways to represent t as pq so that gcd(p,q) = 1 to the answer. This in fact can be easily calculated as 2w, where w is the number of distinct prime divisors of t. You’re encouraged to work out the explanation of this yourself.

The main idea of this problem is thus doing a loop for gcd(x,y), not for x or y. Note that it can also be solved for a,b,c ≤ 109 as there’s still a small number of possible values of d. While this problem probably looks like a math problem much, I still hope you enjoyed it :slight_smile:


Can be found here.


Can be found here.