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
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 !!!
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
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
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