11417 - GCD

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
pfiesteria
New poster
Posts: 9
Joined: Mon Aug 13, 2007 7:45 am

11417 - GCD

Post by pfiesteria » Sun Mar 16, 2008 8:07 am

solved!
    Last edited by pfiesteria on Mon Mar 17, 2008 8:09 am, edited 1 time in total.

    User avatar
    emotional blind
    A great helper
    Posts: 383
    Joined: Mon Oct 18, 2004 8:25 am
    Location: Bangladesh
    Contact:

    Post by emotional blind » Sun Mar 16, 2008 8:38 am

    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); 

    pfiesteria
    New poster
    Posts: 9
    Joined: Mon Aug 13, 2007 7:45 am

    Post by pfiesteria » Sun Mar 16, 2008 12:16 pm

    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!

    User avatar
    emotional blind
    A great helper
    Posts: 383
    Joined: Mon Oct 18, 2004 8:25 am
    Location: Bangladesh
    Contact:

    Post by emotional blind » Sun Mar 16, 2008 1:27 pm

    Its better to remove your code after getting accepted.

    turcse143
    Learning poster
    Posts: 81
    Joined: Wed May 09, 2007 9:59 pm
    Location: (CSE,DU) Dhaka,Bangladesh

    Post by turcse143 » Wed Mar 19, 2008 10:01 pm

    for the minimizing time it is better to use the
    phi() function to generate the solution.
    ''I want to be most laziest person in the world''

    rusho_eu
    New poster
    Posts: 2
    Joined: Thu Nov 05, 2009 10:11 pm

    Re: 11417 - GCD

    Post by rusho_eu » Thu Nov 05, 2009 10:34 pm

    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;
    }
    

    Greus
    New poster
    Posts: 2
    Joined: Sun Sep 16, 2007 2:01 am

    Re: 11417 - GCD

    Post by Greus » Thu Aug 12, 2010 12:07 am

    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

    shoaib7k
    New poster
    Posts: 10
    Joined: Thu Aug 18, 2011 7:45 pm

    Re: 11417 - GCD

    Post by shoaib7k » Thu Aug 18, 2011 10:33 pm

    can i solve 11424 in this way.....
    if i give same code .... verdict is time limit......

    jokerz
    New poster
    Posts: 8
    Joined: Tue Nov 05, 2013 10:24 am

    11417 GCD

    Post by jokerz » Mon Dec 30, 2013 5:27 pm

    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.... :-?

    brianfry713
    Guru
    Posts: 5947
    Joined: Thu Sep 01, 2011 9:09 am
    Location: San Jose, CA, USA

    Re: 11417 GCD

    Post by brianfry713 » Wed Jan 15, 2014 3:17 am

    Check input and AC output for thousands of problems on uDebug!

    User avatar
    uDebug
    A great helper
    Posts: 475
    Joined: Tue Jul 24, 2012 4:23 pm

    Re: 11417 - GCD

    Post by uDebug » Tue May 13, 2014 2:44 pm

    Replying to follow the thread.
    Check input and AC output for over 7,500 problems on uDebug!

    Find us on Facebook. Follow us on Twitter.

    User avatar
    uDebug
    A great helper
    Posts: 475
    Joined: Tue Jul 24, 2012 4:23 pm

    Re: 11417 GCD

    Post by uDebug » Tue May 13, 2014 2:45 pm

    Replying to follow the thread.
    Check input and AC output for over 7,500 problems on uDebug!

    Find us on Facebook. Follow us on Twitter.

    Post Reply

    Return to “Volume 114 (11400-11499)”