1627：【例 3】最大公约数

1627：【例 3】最大公约数

时间限制: 1000 ms         内存限制: 524288 KB
提交数: 592     通过数: 72

【题目描述】

给出两个正整数 A,B

，求它们的最大公约数。

【输入】

输入共两行，第一行一个正整数 A

，第二行一个正整数 B

。

【输出】

在第一行输出一个整数，表示 A,B

的最大公约数。

【输入样例】

18
24

【输出样例】

6

【提示】

数据范围与提示：

对于 60% 的数据，1≤A,B≤1018

；

对于 100% 的数据，1≤A,B≤103000

。

其实这道题就是裸高精，十分的简单，因为我的脑壳有问题打完之后自信满满却发现漏洞百出，调了一个小时才搞好。。。

#include<bits/stdc++.h>
using namespace std;
const int base=10000;
int a[10000],b[10000],c[10000],f[10000],T;
 void Print(int a[])
{
    int i,j;
    cout<<a[a[0]];
    for(i=a[0]-1;i>0;i--)
     for(j=base/10;j>0;j/=10) cout<<a[i]/j%10;
}
 void Init(int a[])
{
    string s;
    cin>>s;
    int len=s.length(),i,j;
    for(i=0;i<len;i++)
    {
        j=(len-i+3)/4;
        a[j]=a[j]*10+s[i]-'0';
    }
    a[0]=(len+3)/4;
}
 int Compare(int a[],int b[])
{
    if(a[0]>b[0]) return 1;
    if(a[0]<b[0]) return -1;
    for(int i=a[0];i>=1;i--)
    {
        if(a[i]>b[i]) return 1;
        else if(a[i]<b[i]) return -1;
    }
    return 0;
}
 void Div(int a[],int k)
{
    int i,t=0;
    for(i=a[0];i>=1;i--)
    {
        t=t*base+a[i];
        a[i]=t/k;
        t%=k;
    }
    while(a[a[0]]==0&&a[0]>0) a[0]--;
}
 void Minus(int a[],int b[])
{
    for(int i=1;i<=a[0];i++)
    {
        a[i]-=b[i];
        if(a[i]<0)
        {a[i+1]--;
            a[i]+=base;
            
        }
    }
    while(a[a[0]]==0&&a[0]>0) a[0]--;
}
void Gcd(int a[],int b[],int t)
{
    if(Compare(a,b)==0) 
    {
        T=t;
        return ;
    }
    if(Compare(a,b)<0)
    {
        Gcd(b,a,t);
        return ;
    }
    int ta,tb;
    if(a[1]%2==0){Div(a,2);ta=1;}
    else ta=0;
    if(b[1]%2==0){Div(b,2);tb=1;}
    else tb=0;
    if(ta&&tb) Gcd(a,b,t+1);
    else if(!ta&&!tb)
    {
        Minus(a,b);Gcd(a,b,t);
    }
    else Gcd(a,b,t);
}
 void MulHigh(int a[],int b[])
{
    memset(c,0,sizeof(c));
    int i,j;
    for(i=1;i<=a[0];i++)
     for(j=1;j<=b[0];j++)
    {
        c[i+j-1]+=a[i]*b[j];
        c[i+j]+=c[i+j-1]/base;
        c[i+j-1]%=base;
    }
    c[0]=a[0]+b[0];
    while(c[c[0]]==0&&c[0]>0) c[0]--;
    for(i=0;i<=c[0];i++) a[i]=c[i];
}
 void MulLow(int a[],int k)
{
    int i;
    for(int i=1;i<=a[0];i++)
    {
        a[i]*=k;
    }
    for(int i=1;i<=a[0];i++)
    {
        a[i+1]+=a[i]/base;
        a[i]%=base;
    }
    while(a[a[0]+1]>0)
    {
        a[0]++;
        a[a[0]+1]=a[a[0]]/base;
        a[a[0]]%=base;
    }
}
int main()
{
    Init(a);Init(b);
    Gcd(a,b,0);
    if(T==0) Print(a);
    else
    {
        f[0]=f[1]=1;
        for(int i=1;i<=T;i++) MulLow(f,2);
        MulHigh(f,a);
        Print(f);
    }
    return 0;
}