Thread: solve efficiently

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Are you familiar with the Euclidean Algorithm? http://mathworld.wolfram.com/EuclideanAlgorithm.html

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

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    please

    can u repost explaining it please

    my campus has blocked that site ( stupid proxy restrictions )

    sorry of the trouble
    thank u very much

  4. #4
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. solving efficiently
    By jack_carver in forum C++ Programming
    Replies: 1
    Last Post: 02-20-2009, 07:54 AM
  2. how to compute set intersection efficiently?
    By George2 in forum C Programming
    Replies: 4
    Last Post: 06-02-2006, 09:06 AM
  3. Replies: 2
    Last Post: 04-25-2005, 11:59 AM
  4. Plz solve my problem !
    By pankaj8096 in forum C Programming
    Replies: 12
    Last Post: 01-16-2003, 12:59 AM
  5. Help to solve this problem
    By Romashka in forum C++ Programming
    Replies: 3
    Last Post: 04-16-2002, 09:32 AM