solving efficiently

This is a discussion on solving efficiently within the C++ Programming forums, part of the General Programming Boards category; 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 ...

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

    solving 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 ( also for ex: 45,100 is same as 100,45 )

    here is what i do
    Code:
    	lim=N/2;
    
    	for(i=2;i<=lim;i++)
    
    	{
    
    		for(j=N-i+1;j<=N;j++)
    
    			if(i+j-gcd(i,j)==N)
    	count++;
    
    	}
    
    	printf("%d",count+2);
    N<10^6

    can any 1 help !!!

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Cross posted: solve efficiently

    --
    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. solve efficiently
    By jack_carver in forum C Programming
    Replies: 4
    Last Post: 02-20-2009, 07:56 AM
  2. how to compute set intersection efficiently?
    By George2 in forum C Programming
    Replies: 4
    Last Post: 06-02-2006, 10:06 AM
  3. JOB: C/C++ Developer with problem solving skills
    By VoltRecruiter in forum Projects and Job Recruitment
    Replies: 1
    Last Post: 01-26-2006, 12:25 AM
  4. Solving A Maze Using C Language!!!!
    By jonnybgood in forum C Programming
    Replies: 6
    Last Post: 11-08-2005, 12:15 PM
  5. Sign-up Thread: Problem Solving #1
    By ygfperson in forum Contests Board
    Replies: 15
    Last Post: 01-26-2003, 02:55 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21