11417 - GCD

[pfiesteria]

solved!

[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]

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]

Its better to remove your code after getting accepted.

[turcse143]

for the minimizing time it is better to use the
phi() function to generate the solution.

[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]

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]

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

[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]

That code gets TLE.
Try using:
http://en.wikipedia.org/wiki/Euclidean_algorithm

[uDebug]

Replying to follow the thread.

[uDebug]

Replying to follow the thread.