解题报告 P2152 [SDOI2009]SuperGCD

题目内容

P2152

高精求两数 gcd

解题思路

使用辗转相除法求gcd的话不仅不方便实现高精，而且容易 T ，所以这里使用更相减损术。

老祖宗的方法真香

具体思路：

\begin{aligned}
\gcd(a,b)&=2\gcd(a/2,b/2)\quad&(2\mid a, 2\mid b)\
\gcd(a,b)&=\gcd(a/2,b)\quad&(2\mid a,2\not\mid b)\
\gcd(a,b)&=\gcd(a-b,b)\quad&(2\not\mid a,2\not\mid b,a>b)
\end{aligned}

依次解下去就可了，注意高精即可，代码有点麻烦，不要用递归容易爆栈

这题我一开始提交的时候莫名RE，结果发现是判断函数cmp写挂了，表示绝望调了好久qwq。

#include <cstdio>
#include <vector>
#include <cctype>
#include <algorithm>
using namespace std;

typedef vector<int> bigint;
bigint _minus(bigint, bigint);
bigint _times(bigint, bigint);
void div2(bigint&);
void print(bigint);
inline bool isodd(bigint&);

bigint _minus(bigint a, bigint b)//高精减法
{
    for(int i=0;i<b.size();i++)
    {
        a[i]=a[i]-b[i];
        if(a[i]<0)
        {
            a[i+1]--;
            a[i]+=10;
        }
    }
    for(int i=b.size();i<a.size();i++)
    {
        if(a[i]<0)
            a[i+1]--,a[i]+=10;
    }
    for(int i=a.size()-1;i>0;i--)
    {
        if(a[i])
            break;
        if(!a[i])
            a.pop_back();
    }
    return a;
}

bigint _times(bigint a, bigint b)//高精乘法
{
    bigint ans;
    int la=a.size(),lb=b.size();
    for(int i=0;i<la+lb;i++)
        ans.push_back(0);
    for(int i=0;i<lb;i++)
    {
        for(int j=0;j<la;j++)
        {
            ans[i+j]+=a[j]*b[i];
            if(ans[i+j]>=10)
            {
                ans[i+j+1]+=ans[i+j]/10;
                ans[i+j]%=10;
            }
        }
    }
    for(int i=ans.size()-1;i>0;i--)
    {
        if(ans[i])
            break;
        else
            ans.pop_back();
    }
    return ans;
}

void div2(bigint &a)
{
    for(int i=a.size()-1;i>=0;i--)
    {
        if(a[i]&1)
            a[i-1]+=10;
        a[i]/=2;
    }
    if(!a.back())
        a.pop_back();
}

bigint read()
{
    bigint ans;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        ans.push_back(c-'0');
        c=getchar();
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

void print(bigint a)
{
    for(int i=a.size()-1;i>=0;i--)
        printf("%d",a[i]);
    printf("\n");
    return;
}

inline bool isodd(bigint &a)//判断其是否为奇数
{
    return a.front()&1;
}

bool cmp(bigint a, bigint b)//return a>b
{
    if(a.size()>b.size())
        return true;
    else if(a.size()<b.size())
        return false;
    else
    {
        for(int i=a.size()-1;i>=0;i--)
            if(a[i]>b[i])
                return true;
            else if(a[i]!=b[i])
                return false;
    }
    return false;
}

int main()
{
    bigint a=read(),b=read();
    bigint tag={1},two={2};
    while(a!=b)//当a=b时zhong
    {
        if(!isodd(a) && !isodd(b))
        {//如果都是偶数那就都除以二然后标签乘二
            div2(a);
            div2(b);
            tag=_times(tag,two);
        }
        else if(!isodd(a))//如果a是偶数
            div2(a);//除以二
        else if(!isodd(b))//如果b是偶数
            div2(b);//除以二
        else
        {
            if(cmp(a,b))//判断哪个更大然后辗转相减
                a=_minus(a,b);
            else
                b=_minus(b,a);
        }
    }
    print(_times(a,tag));//返回的是最终结果乘上tag
    return 0;
}