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=9;
const int N=10010;
char s1[N],s2[N];
ll a[N],b[N];
int la=0,lb=0;
inline int pan(){
    if(la>lb)return 0;
    if(la<lb)return 1;
    for(int i=la-1;i>=0;i--){
    if(a[i]>b[i])return 0;
    if(a[i]<b[i])return 1;
    }
    return 2;
}
void diva(){
    for(int i=la-1;i>=0;i--){
    if(!(a[i]&1))a[i]>>=1;
    else{
        a[i-1]+=big;
        a[i]>>=1;
    }
    }
　　if(!a[la-1])la--;
    return;
}
void divb(){
    for(int i=lb-1;i>=0;i--){
    if(!(b[i]&1))b[i]>>=1;
    else{
        b[i-1]+=big;
        b[i]>>=1;
    }
    }
    if(!b[lb-1])lb--;
    return;
}
int change(char s[],ll n[]){
    char temp[N];
    int l=strlen(s),cur=0;
    while(l/p){
    strncpy(temp,s+l-p,p);
    n[cur++]=atoi(temp);
    l-=p;
    }
    if(l){
    memset(temp,0,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=0;
void gcd(){
    while(233){
    int a_2=0,b_2=0;
    while(!(a[0]&1)){diva();a_2++;}
    while(!(b[0]&1)){divb();b_2++;}
    k_2+=min(a_2,b_2);
    int pi=pan();
    if(pi==0){
        for(int i=0;i<la;i++){
        if(a[i]<b[i]){
            a[i]+=big;
            a[i+1]--;
        }
        a[i]=a[i]-b[i];
        }
        for(int i=la-1;i>=0;i--){
        if(a[i])break;
        else la--;
        }
    }else if(pi==1){
        for(int i=0;i<lb;i++){
        if(b[i]<a[i]){
            b[i]+=big;
            b[i+1]--;
        }
        b[i]=b[i]-a[i];
        }
        for(int i=lb-1;i>=0;i--){
        if(b[i])break;
        else lb--;
        }
    }else return;
    }
    return;
}
int main(){
    init();
    gcd();
    for(int i=1;i<=k_2;i++){
    for(int j=0;j<la;j++){
        a[j]<<=1;
    }
    for(int j=0;j<la;j++){
        if(a[j]>big){
        a[j+1]+=a[j]/big;
        a[j]%=big;
        if(j+1>=la)la++;
        }
    }
    }
    printf("%lld",a[la-1]);
    for(int i=la-2;i>=0;i--){
    printf("%0*lld",p,a[i]);
    }
    printf("
");
    return 0;
}