洛谷 P2152 [SDOI2009]SuperGCD 题解【数学】【gcd】【高精度】

点击量：193

    发现了辗转相除法的劣势

目录

题目描述

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。

 

输入输出格式

输入格式：

共两行： 第一行：一个数A。 第二行：一个数B。

 

输出格式：

一行，表示A和B的最大公约数。

 

输入输出样例

输入样例#1：

12
54

输出样例#1：

6

说明

对于20%的数据，0 < A , B ≤ 10 ^ 18。 对于100%的数据，0 < A , B ≤ 10 ^ 10000。

题解：

    对于1e10000的数据，高精肯定是免不了。不过一般求GCD都是欧几里得辗转相除法，但是对高精来说，除法的时间复杂度可以达到$ O(N^2)$，其中包含了每次计算时的移位（也就是有$ N$这么大的常数），再加上各种大常数和欧几里得算法自带的$ O(\log N)$，算法复杂度达到$ O(N^2\log N)$，对于$ N=10,000$的数据是不可能实现的。(文中的N全部指位数)

    不过更相减损术这种看上去更慢的解法是可以帮助高精完成这个事情的。在学习更相减损术时，我们可以发现，对于两个正在被处理的数，设为$ a,b$，如果他们两个都是偶数，那么它们一定有一个公因数为2，此时将$ a,b$同除上2；如果$ a,b$中只有一个为偶数，那这两个数中肯定没有2这个公因数，将为偶数的那个数除上2；如果$ a,b$均为奇数，那么根据更相减损术，就用大的减去小的，于是会出现一个偶数，可以继续进行上面一步操作。

    这样一来，我们每两步都至少会把一个数除以2，这个常数比较小，可以忽略不计。在高精度的计算中，我们无论是乘2还是除以2都很方便，只用花$ O(N)$的时间就能完成。而这个过程中不断除以2，总共约进行了$ \log n$次，因此时间复杂度为$ O(N\log N)$。

    这个题如果不压位可能会有常数问题，而且没有过多的乘法加法等计算，所以可以用long long压到15位左右。当然，在时间宽裕的情况下压4位或8位就足够了。

Code：

#include<cstdio>
#include<cstring>
#include<iostream>
using std::cin;
using std::string;
int ten[5]={1000,1,10,100};
struct lll
{
    int num[3000];
    lll(string s)
    {
        memset(num,0,sizeof(num));
        num[0]=s.size()/4+1;
        int len=s.size();
        for(int i=1;i<=len;i++)
            num[(i-1)/4+1]+=(s[len-i]-'0')*ten[i%4];
    }
    friend bool operator <(lll a,lll b)
    {
        if(a.num[0]!=b.num[0])
            return a.num[0]<b.num[0];
        for(int i=a.num[0];i>=1;i--)
            if(a.num[i]!=b.num[i])
                return a.num[i]<b.num[i];
        return false;
    }
    friend lll operator -(lll a,lll b)
    {
        for(int i=1;i<=a.num[0];i++)
        {
            a.num[i]-=b.num[i];
            if(a.num[i]<0)
            {
                a.num[i]+=10000;
                a.num[i+1]--;
            }
        }
        while(!a.num[a.num[0]])
            a.num[0]--;
        return a;
    }
    void Double()
    {
        for(int i=1;i<=num[0];i++)
        {
            num[i]*=2;
            if(num[i-1]>=10000)
            {
                num[i]++;
                num[i-1]-=10000;
            }
        }
        if(num[num[0]+1])
            num[0]++;
    }
    void Divide()
    {
        for(int i=num[0];i>=1;i--)
        {
            if(num[i]&1)
                num[i-1]+=10000;
            num[i]/=2;
        }
        while(!num[num[0]])
            num[0]--;
    }

};
lll gcd(lll a,lll b)
{
    int cnt=0;
    while(a<b||b<a)
    {
        if(!(a.num[1]&1)&&!(b.num[1]&1))
        {
            a.Divide();
            b.Divide();
            //c.Double();
            ++cnt;
        }
        else if(!(a.num[1]&1))
            a.Divide();
        else if(!(b.num[1]&1))
            b.Divide();
        else
        {
            if(a<b)
            {
                lll t=a;
                a=b;
                b=t;
            }
            a=a-b;
        }
    }
    for(int i=1;i<=cnt;i++)
        a.Double();
    return a;
}
void print(lll a)
{
    printf("%d",a.num[a.num[0]]);
    for(int i=a.num[0]-1;i;i--)
    {
        if(a.num[i]<1000)
            printf("0");
        if(a.num[i]<100)
            printf("0");
        if(a.num[i]<10)
            printf("0");
        printf("%d",a.num[i]);
    }
    return;
}
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    lll a(s1),b(s2);
    print(gcd(a,b));
    return 0;
}