×

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 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 :)

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

10.8k346472486
accept rate: 36%

 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Tags:

×2,700
×556
×5
×1

Seen: 539 times

Last updated: 22 Nov '12, 11:44