### 11417 - GCD

Posted:

**Sun Mar 16, 2008 8:07 am**solved!

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=42&t=37069

Page **1** of **1**

Posted: **Sun Mar 16, 2008 8:07 am**

solved!

Posted: **Sun Mar 16, 2008 8:38 am**

your GCD function doesn't return if x!=0 && y!=0.

changeto

change

Code: Select all

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

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**

Yes, you are right! thanks a lot!emotional blind wrote:your GCD function doesn't return if x!=0 && y!=0.

changetoCode: Select all

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

Code: Select all

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

Posted: **Sun Mar 16, 2008 1:27 pm**

Its better to remove your code after getting accepted.

Posted: **Wed Mar 19, 2008 10:01 pm**

for the minimizing time it is better to use the

phi() function to generate the solution.

phi() function to generate the solution.

Posted: **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..

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

Posted: **Thu Aug 12, 2010 12:07 am**

your solution is wrong because of this part of the code:
you should change it for this one:

and maybe your solution get TLE because of the recursive function gcd, good luck

Code: Select all

```
if(N==1)
{
G=1;
}
```

Code: Select all

```
if(N==1)
{
G=0;
}
```

Posted: **Thu Aug 18, 2011 10:33 pm**

can i solve 11424 in this way.....

if i give same code .... verdict is time limit......

if i give same code .... verdict is time limit......

Posted: **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....

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

Posted: **Wed Jan 15, 2014 3:17 am**

Posted: **Tue May 13, 2014 2:44 pm**

Replying to follow the thread.

Posted: **Tue May 13, 2014 2:45 pm**

Replying to follow the thread.