Stein算法是一种计算两个数的算法，是针对在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。

算法思想：

由J. Stein 1961年提出的Stein算法很好的解决了 中的这个缺陷，Stein算法只有整数的移位和加减法，为了说明Stein算法的正确性，首先必须注意到以下结论：

gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。

gcd(ka,kb)=k gcd(a,b)，也就是 运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的 必然能被2整除。

当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响 。特殊地，当k=2时，说明计算一个偶数和一个奇数的 时，可以先将偶数除以2。

算法步骤：

1、如果An=Bn,那么An(或Bn)*Cn是 ,算法结束

2、如果An=0，Bn是 ，算法结束

3、如果Bn=0，An是 ，算法结束

4、设置A1=A、B1=B和C1=1

5、如果An和Bn都是偶数，则An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)

6、如果An是偶数，Bn不是偶数，则An+1=An/2，Bn+1=Bn，Cn+1=Cn(很显然啦，2不是奇数的约数)

7、如果Bn是偶数，An不是偶数，则Bn+1=Bn/2，An+1=An，Cn+1=Cn(很显然啦，2不是奇数的约数)

8、如果An和Bn都不是偶数，则An+1=|An-Bn|/2，Bn+1=min(An,Bn)，Cn+1=Cn

9、n加1，转1

 

简单来看就是：

对于求a,b的GCD(a,b)有：

若a为奇数，b为偶数，GCD(a,b)=GCD(a,b/2)

若a为偶数，b为奇数，GCD(a,b)=GCD(a/2,b)

若a为偶数，b为偶数，GCD(a,b)=2*GCD(a/2,b/2)

若a为奇数，b为奇数，GCD(a,b)=GCD(a-b,b) (a>b) 或 GCD(a,b-a) (b>a)

 

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

输入输出格式

输入格式：

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

 

输出格式：

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

 

输入输出样例

输入样例#1：

1254

输出样例#1：

6

说明

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

对于100%的数据，0 < A , B ≤ 10 ^ 10000。（令人惊恐的数据）

解法：压位+stein算法

代码如下：

 

#include
       
        #define inf 1000000000using namespace std;char ch1[10005],ch2[10005];int la,lb,cnt;struct data{    int a[1205],l;}a,b;bool com(){
     //判断大小     if (a.l
        
         b.l) return 1;    for (int i=a.l;i>0;i--)            if (a.a[i]>b.a[i]) return 1;        else if (a.a[i]
         
          0;i--)        if (i==a.l) printf("%d",a.a[i]);        else printf("%09d",a.a[i]);//因为压了位 特判中间是否有0的情况 }data sub(data a,data b){
      //相减     int k; data c;    for (int i=1;i<=1200;i++){        if (i<=b.l) c.a[i]=a.a[i]-b.a[i];        else if (i<=a.l) c.a[i]=a.a[i];        else c.a[i]=0;        if (c.a[i]<0){            c.a[i]+=inf;            a.a[i+1]--;        }    }    c.l=a.l;    while (c.a[c.l]==0&&c.l) c.l--;    return c;}void diva(){
     // a除2     for (int i=1;i<=a.l;i++){        if (a.a[i]&1) a.a[i-1]+=inf/2;        a.a[i]>>=1;    }    if (!a.a[a.l]) a.l--;}void divb()// b除2 {    for (int i=1;i<=b.l;i++){        if (b.a[i]&1) b.a[i-1]+=inf/2;        b.a[i]>>=1;    }    if (!b.a[b.l]) b.l--;}void mul(){ // a b 都×2     for (int i=a.l;i>0;i--){        a.a[i]<<=1;        a.a[i+1]+=a.a[i]/inf;        a.a[i]%=inf;    }    while (a.a[a.l]>0) a.l++;    for (int i=b.l;i>0;i--){        b.a[i]<<=1;        b.a[i+1]+=b.a[i]/inf;        b.a[i]%=inf;    }    while (b.a[b.l]>0) b.l++;}int main(){    //读入数据     scanf("%s%s",ch1+1,ch2+1);    la=strlen(ch1+1); lb=strlen(ch2+1);     if (la%9) a.l=la/9+1; else a.l=la/9;    if (lb%9) b.l=lb/9+1; else b.l=lb/9;    for (int i=1;i<=a.l;i++){        int k1=max(1,la-i*9+1),k2=la-(i-1)*9;        for (int j=k1;j<=k2;j++) a.a[i]=a.a[i]*10+ch1[j]-'0';    }    for (int i=1;i<=b.l;i++){        int k1=max(1,lb-i*9+1),k2=lb-(i-1)*9;        for (int j=k1;j<=k2;j++) b.a[i]=b.a[i]*10+ch2[j]-'0';    }    while (1){        if ((a.a[1]%2==0)&&(b.a[1]%2==0)) {            diva();            divb();            cnt++;    //这里的cnt是指出现了多少次 a，b都是偶数的情况，在最后的时候再把cnt个2乘回去 （参见最上方算法）        }         else if (a.a[1]%2==0)             diva();        else if (b.a[1]%2==0)             divb();        if (com()){
     // a大的情况             a=sub(a,b);             if (!a.l) {                while (cnt--)                      mul();                 print(b);                 break;            }        }        else { //b大的情况             b=sub(b,a);             if (!b.l) {                while (cnt--)                     mul();                 print(a);                break;            }        }    }    return 0;}