## 11417 - GCD

Moderator: Board moderators

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

### 11417 - GCD

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
Contact:
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
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
Contact:
Its better to remove your code after getting accepted.

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 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

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

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

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

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+ ....
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

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

Check input and AC output for over 7,500 problems on uDebug!