BZOJ1876：[SDOI2009]SuperGCD——C++高精度良心题解

http://www.lydsy.com/JudgeOnline/problem.php?id=1876

Description

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约数）！因此他经常和别人比

赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给Sheng bill岂不是很丢脸！所以你

决定写一个程序来教训他。

Input

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

0 < A , B ≤ 10 ^ 10000。

Output

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

Sample Input

12
54

Sample Output

——————————————————————————————————

如果你会写大整数除法，请跳过这个博客。

要做这道题：

1.我们要压位，对于压位默认看博客的人已经会了，如果不会请baidu。

2.我们需要三个gcd的应用

　　1.gcd(a,b)=k*gcd(a/k,b/k)(a%k==0,b%k==0)

　　2.gcd(a,b)=gcd(a/k,b)(a%k==0&&b%k!=0)

　　3.gcd(a,b)=gcd(b,a-b)(a>b)

然后我们每次进行3操作的时候，用1和2操作来预先分离出来k，减少计算量。

这里取k=2，我们发现这种操作有着很妙的优化：

对于每次操作3，如果是：

　　1.至少一个偶数，那么就1或2操作，至少减少了其中一个数一半的大小。

　　2.无偶数，则3操作之后一定能变成1情况。

所以我们大概是能减少一半的运算量，这明显十分的妙！

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll big=1e9;

const int p=;

const int N=;

char s1[N],s2[N];

ll a[N],b[N];

int la=,lb=;

inline int pan(){

    if(la>lb)return ;

    if(la<lb)return ;

    for(int i=la-;i>=;i--){

    if(a[i]>b[i])return ;

    if(a[i]<b[i])return ;

    }

    return ;

}

void diva(){

    for(int i=la-;i>=;i--){

    if(!(a[i]&))a[i]>>=;

    else{

        a[i-]+=big;

        a[i]>>=;

    }

    }
　　if(!a[la-])la--;

    return;

}

void divb(){

    for(int i=lb-;i>=;i--){

    if(!(b[i]&))b[i]>>=;

    else{

        b[i-]+=big;

        b[i]>>=;

    }

    }

    if(!b[lb-])lb--;

    return;

}

int change(char s[],ll n[]){

    char temp[N];

    int l=strlen(s),cur=;

    while(l/p){

    strncpy(temp,s+l-p,p);

    n[cur++]=atoi(temp);

    l-=p;

    }

    if(l){

    memset(temp,,sizeof(temp));

    strncpy(temp,s,l);

    n[cur++]=atoi(temp);

    }

    return cur;

}

void init(){

    scanf("%s%s",s1,s2);

    la=change(s1,a);

    lb=change(s2,b);

    return;

}

int k_2=;

void gcd(){

    while(){

    int a_2=,b_2=;

    while(!(a[]&)){diva();a_2++;}

    while(!(b[]&)){divb();b_2++;}

    k_2+=min(a_2,b_2);

    int pi=pan();

    if(pi==){

        for(int i=;i<la;i++){

        if(a[i]<b[i]){

            a[i]+=big;

            a[i+]--;

        }

        a[i]=a[i]-b[i];

        }

        for(int i=la-;i>=;i--){

        if(a[i])break;

        else la--;

        }

    }else if(pi==){

        for(int i=;i<lb;i++){

        if(b[i]<a[i]){

            b[i]+=big;

            b[i+]--;

        }

        b[i]=b[i]-a[i];

        }

        for(int i=lb-;i>=;i--){

        if(b[i])break;

        else lb--;

        }

    }else return;

    }

    return;

}

int main(){

    init();

    gcd();

    for(int i=;i<=k_2;i++){

    for(int j=;j<la;j++){

        a[j]<<=;

    }

    for(int j=;j<la;j++){

        if(a[j]>big){

        a[j+]+=a[j]/big;

        a[j]%=big;

        if(j+>=la)la++;

        }

    }

    }

    printf("%lld",a[la-]);

    for(int i=la-;i>=;i--){

    printf("%0*lld",p,a[i]);

    }

    printf("\n");

    return ;

}

巴特西