# GCD of large numbers

Discussion in 'C' started by manjotpahwa, May 31, 2010.

1. ### manjotpahwaNew Member

Joined:
Apr 14, 2010
Messages:
6
0
Trophy Points:
0
I have tried to solve this question on some website and I have literally tested my code for about 240 digits long integers but still the site says that my answer is wrong. Can you please tell me where it is, the question is as follows:

Input

The first line of the input file contains a number representing the number of lines to follow. Each line consists of two number A and B (0 <= A <= 40000 and A <= B < 10^250).
Output:

Print for each pair (A,B) in the input one integer representing the GCD of A and B.

My code is as follows:

Code:
```#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int num;
int main()
{int k=0, i, A, temp, digits, ans, test;
char s;
scanf("%d", &test);
for(i=0;i<test;i++)
{
scanf("%d %s", &A, s);
k=stringtoint(s);
temp=A;
digits=0;
while(temp)
{
digits++;
temp/=10;
}
ans=divideB(digits, A, k); printf("%d\n", ans);
}
return 0;
}
int stringtoint(char s[])
{
int i, len=strlen(s), k=0;
for(i=0;i<len;i++)
{num[k++]=s[i]-'0';}
return k;
}
int divideB(int digits, int A, int k)
{
unsigned int j=0, i=k-1, ans, d, count=digits+1, b=0;
for(i=k-(digits);i<k;i++)
{
b=(10*b)+num[i];
}
printf("%d\n", b);
if(b<10*A) ans = gcd(b, A);
else
{
d = pow(10,digits);
b = b%d;
ans = gcd(b,A);
}
return ans;
}
int gcd(int a, int b)
{
if (b==0)
return a;
else
return gcd(b,a%b);
}```

Last edited by a moderator: May 31, 2010