You are not logged in. Please login at www.codechef.com to post your questions!

×

EQUATIO - Editorial

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 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".

asked 22 Nov '12, 11:44

admin's gravatar image

admin ♦♦
9.9k346469475
accept rate: 36%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Tags:

×1,458
×334
×5
×1

Asked: 22 Nov '12, 11:44

Seen: 457 times

Last updated: 22 Nov '12, 11:44