i need to solve this equation efficiently

m+n-gcd(m,n)=N

i.e, when N is given i need to find NUMBER OF PAIRS of m,n that satisify the equation

N<10^6

can any 1 help !!!

Printable View

- 02-20-2009jack_carversolve efficiently
i need to solve this equation efficiently

m+n-gcd(m,n)=N

i.e, when N is given i need to find NUMBER OF PAIRS of m,n that satisify the equation

N<10^6

can any 1 help !!! - 02-20-2009zacs7
Are you familiar with the Euclidean Algorithm? http://mathworld.wolfram.com/EuclideanAlgorithm.html

That's generally what these sort of questions are getting at. - 02-20-2009jack_carverplease
can u repost explaining it please

my campus has blocked that site ( stupid proxy restrictions )

sorry of the trouble

thank u very much - 02-20-2009jack_carvergcd ?
i think i need to reduce two things to get proper runtime

i should not be looping for each & every case & also shud not use recursion to calculate gcd ( euclids algo will help)

but what about the for loops ??

some 1 help

thank u - 02-20-2009matsp
Why don't you google for Euclidian Algorithm then - there are probably hundreds of places where it is descrbed. [And I'm pretty sure that you are not SUPPOSED to come up with that solution by yourself - that's what books about algorithms are for, if you aren't able to use the web].

--

Mats