# PROBLEM LINKS

Practice

Contest

# DIFFICULTY

MEDIUM

# EXPLANATION

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 10^{6}). 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 2^{w}, 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** ≤ 10^{9} 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 :)

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

asked
**22 Nov '12, 11:44**

admin ♦♦

11.1k●346●472●490

accept rate:
36%