1. ## solve 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 !!!

2. Are you familiar with the Euclidean Algorithm? http://mathworld.wolfram.com/EuclideanAlgorithm.html

That's generally what these sort of questions are getting at.

can u repost explaining it please

my campus has blocked that site ( stupid proxy restrictions )

sorry of the trouble
thank u very much

4. ## gcd ?

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

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