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 »

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

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

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

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

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

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

    Post by emotional blind »

    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 »

    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 »

    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 »

    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 »

    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 »

    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 »

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

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

    Re: 11417 - GCD

    Post by uDebug »

    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.

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

    Re: 11417 GCD

    Post by uDebug »

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