Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   GCD of large numbers (http://www.go4expert.com/forums/gcd-t22271/)

manjotpahwa 31May2010 19:08

GCD of large numbers
 
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[251];
int main()
{int k=0, i, A, temp, digits, ans, test;
char s[252];
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);
}



All times are GMT +5.5. The time now is 10:08.