LOJ10205 最大公约数

题意

给出 $A,B$ ，求 $gcd(A,B)$ 。

其中 $A,B\le 10^{3000}$ 。

题解

数据范围很大，显然要用二进制求 $gcd$ 。其它都是板子。

#include<bits/stdc++.h>

using namespace std;

struct bigint {
    int len,s[3005];
    bigint() { memset(s,0,sizeof(s)); len=0; }
} A,B;
char ch[3005];

inline void read(bigint &x)
{
    int len=strlen(ch);
    x.len=len;
    for (int i=len-1;i>=0;i--) x.s[len-i]=ch[i]-'0';
}

inline bigint division(bigint x,int y)
{
    bigint z;
    int sum=0,len=x.len;
    for (int i=len;i;i--)
    {
        sum=sum*10+x.s[i];
        z.s[i]=sum/y;
        sum%=y;
    }
    while (!z.s[len]) len--;
    z.len=len;
    return z;
}

inline bigint sub(bigint x,bigint y) //x>y
{
    bigint z;
    int add=0,len=x.len;
    for (int i=1;i<=len;i++)
    {
        z.s[i]=x.s[i]-y.s[i]-add;
        add=0;
        if (z.s[i]<0) add=1,z.s[i]+=10;
    } 
    z.len=len;
    return z;
}

inline bigint times(bigint x,int y)
{
    bigint z;
    int len=x.len,add=0;
    for (int i=1;i<=len;i++)
    {
        z.s[i]=x.s[i]*y+add;
        add=z.s[i]/10;
        z.s[i]%=10;
    }
    while (add) 
    {
        z.s[++len]=add%10;
        add/=10;
    }
    z.len=len;
    return z;
}

inline int cmp(bigint x,bigint y)
{
    if (x.len>y.len) return 1;
    if (x.len<y.len) return -1;
    for (int i=x.len;i;i--)
    {
        if (x.s[i]<y.s[i]) return -1;
        if (x.s[i]>y.s[i]) return 1;
    }
    return 0;
}

inline void print(bigint x) { for (int i=x.len;i;i--) printf("%d",x.s[i]); }

inline bigint get_sum(bigint x,int y)
{
    while (y--) x=times(x,2);
    return x;
}

inline bigint gcd(bigint x,bigint y)
{
    int i,j;
    for (i=0;x.s[1]%2==0;i++) x=division(x,2);
    for (j=0;y.s[1]%2==0;j++) y=division(y,2);
    i=min(i,j);
    for (;;)
    {
        int cmp_res=cmp(x,y);
        if (cmp_res==0) return get_sum(y,i);
        else if (cmp_res==-1) swap(x,y);
        x=sub(x,y);
        while (x.s[1]%2==0) x=division(x,2);
    }
}

int main()
{
    scanf("%s",ch);
    read(A);
    scanf("%s",ch);
    read(B);
    print(gcd(A,B));
    return 0;
}