UVA 11827 - Maximum GCD(cpp file)

Problem Type : Number Theory


#include<stdio.h>
#include<string.h>
#include<math.h>

long long int gcd(long long int a,long long int b)
{
    long int temp;
    while(b!=0)
    {
        temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}

int main()
{

    long  long  int i,j,k,len,arr[10000],arr1[10000],p,s,l,q,r,g[10000],t,temp,x,y;
    double m;
    char ch[10000];
    scanf("%lld",&t);

        getchar();
        for(x=1;x<=t;x++)
        {
            if(t==0)
                break;
            gets(ch);
            memset(arr1,0,sizeof(arr1));
            p=0;
            len= strlen(ch);
            k=0;
            for(i=0; i<len; i++)
            {
                if( ch[i]>='0' && ch[i]<='9')
                {
                    arr[k] = ch[i]-48;
                    k++;
                }
                l=k-1;
                if(ch[i]>='0' && ch[i]<='9' && ch[i+1]==' ' && k!=0 ||i==len-1)
                {

                    s=0;

                    for(j=l; j>=0; j--)
                    {
                        m=pow(10,s);

                        q =(long long)(m);
                        if(m>q)
                        {
                            q=q+1;
                        }
                        arr1[p]+=arr[j]*q;
                        s++;
                    }
                    k=0;
                    memset(arr,0,sizeof(arr));
                    p++;
                }

            }
            k=0;
            temp=0;
            for(i=0; i<p-1; i++)
            {
                if(arr1[i]==0)
                    continue;
                for(j=i+1; j<p; j++)
                {
                    if(arr1[j]==0)
                        continue;
                    temp=gcd(arr1[i],arr1[j]);


                    if(k<temp)
                    {
                        k = temp;
                    }
                }
            }
                 printf("%lld\n",k);

            memset(ch,'\0',sizeof (ch));
        }

    return 0;
}