Page 1 of 1

11417 - GCD

Posted: Sun Mar 16, 2008 8:07 am
by pfiesteria
solved!

    Posted: Sun Mar 16, 2008 8:38 am
    by emotional blind
    your GCD function doesn't return if x!=0 && y!=0.

    change

    Code: Select all

       if(x<y)GCD(x,y%x);
       else GCD(y,x%y); 
    to

    Code: Select all

       if(x<y)return GCD(x,y%x);
       else return GCD(y,x%y); 

    Posted: Sun Mar 16, 2008 12:16 pm
    by pfiesteria
    emotional blind wrote:your GCD function doesn't return if x!=0 && y!=0.

    change

    Code: Select all

       if(x<y)GCD(x,y%x);
       else GCD(y,x%y); 
    to

    Code: Select all

       if(x<y)return GCD(x,y%x);
       else return GCD(y,x%y); 
    Yes, you are right! thanks a lot!

    Posted: Sun Mar 16, 2008 1:27 pm
    by emotional blind
    Its better to remove your code after getting accepted.

    Posted: Wed Mar 19, 2008 10:01 pm
    by turcse143
    for the minimizing time it is better to use the
    phi() function to generate the solution.

    Re: 11417 - GCD

    Posted: Thu Nov 05, 2009 10:34 pm
    by rusho_eu
    I am new coder and trying to learn. Can any 1 help me?
    I am got wa in the problem 11417 - GCD . I don't know what is the error.
    here is my code..

    Code: Select all

    
    #include<stdio.h>
    
    
    int gcd( int a, int b )
    {
        if( b == 0 ) return a;
        else gcd( b, a % b );
    }
    
    
    int main()
    {
    	int i,N,j;
    	long G=0;
    
    	while(scanf("%d",&N)==1)
    	{
    
    		if(N==0)
    		{
    		
    			break;
    		}
    
    		G=0;
    		for(i=1;i<N;i++)
    		{
    			for(j=i+1;j<=N;j++)
    			{
    				G+=gcd(i,j);
    			}
    		}
    
    
    		if(N==1)
    		{
    		
    			G=1;
    		}
    		printf("%ld\n",G);
    
    	}
    
    
    	return 0;
    }
    

    Re: 11417 - GCD

    Posted: Thu Aug 12, 2010 12:07 am
    by Greus
    your solution is wrong because of this part of the code:

    Code: Select all

    if(N==1)
          {
          
             G=1;
          }
    you should change it for this one:

    Code: Select all

    if(N==1)
          {
          
             G=0;
          }
    and maybe your solution get TLE because of the recursive function gcd, good luck

    Re: 11417 - GCD

    Posted: Thu Aug 18, 2011 10:33 pm
    by shoaib7k
    can i solve 11424 in this way.....
    if i give same code .... verdict is time limit......

    11417 GCD

    Posted: Mon Dec 30, 2013 5:27 pm
    by jokerz
    what is the problem of this code???
    it works for input 10,100 and less than 209 but it doesn't work when input is 210+ ....
    here is the code link:
    http://ideone.com/pxAuWn

    plz someone help meeee.... :-?

    Re: 11417 GCD

    Posted: Wed Jan 15, 2014 3:17 am
    by brianfry713

    Re: 11417 - GCD

    Posted: Tue May 13, 2014 2:44 pm
    by uDebug
    Replying to follow the thread.

    Re: 11417 GCD

    Posted: Tue May 13, 2014 2:45 pm
    by uDebug
    Replying to follow the thread.