1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

GCD of large numbers

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

  1. manjotpahwa

    manjotpahwa New Member

    Joined:
    Apr 14, 2010
    Messages:
    6
    Likes Received:
    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[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);
    }
     
    Last edited by a moderator: May 31, 2010

Share This Page