Stein算法是一种计算两个数最大公约数的算法，是针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。
算法思想：
由J. Stein 1961年提出的Stein算法很好的解决了欧几里德算法中的这个缺陷，Stein算法只有整数的移位和加减法，为了说明Stein算法的正确性，首先必须注意到以下结论：
gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。
算法步骤：
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：
12
54
输出样例#1：
6
说明
对于20%的数据，0 < A , B ≤ 10 ^ 18。
对于100%的数据，0 < A , B ≤ 10 ^ 10000。（令人惊恐的数据）
解法：压位+stein算法
代码如下：
#include<bits/stdc++.h>
#define inf 1000000000
using namespace std;
char ch1[],ch2[];
int la,lb,cnt;
struct data{
int a[],l; }a,b;
bool com(){//判断大小
if (a.l<b.l) return ;
if (a.l>b.l) return ;
for (int i=a.l;i>;i--)
if (a.a[i]>b.a[i]) return ;
else if (a.a[i]<b.a[i]) return ;
return ;
}
void print(data a){//打印结果
while (a.a[a.l]==)
a.l--;
for (int i=a.l;i>;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=;i<=;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]=;
if (c.a[i]<){
c.a[i]+=inf;
a.a[i+]--;
}
}
c.l=a.l;
while (c.a[c.l]==&&c.l) c.l--;
return c;
}
void diva(){// a除2
for (int i=;i<=a.l;i++){
if (a.a[i]&) a.a[i-]+=inf/;
a.a[i]>>=;
}
if (!a.a[a.l]) a.l--;
}
void divb()// b除2
{
for (int i=;i<=b.l;i++){
if (b.a[i]&) b.a[i-]+=inf/;
b.a[i]>>=;
}
if (!b.a[b.l]) b.l--;
}
void mul(){ // a b 都×2
for (int i=a.l;i>;i--){
a.a[i]<<=;
a.a[i+]+=a.a[i]/inf;
a.a[i]%=inf;
}
while (a.a[a.l]>) a.l++;
for (int i=b.l;i>;i--){
b.a[i]<<=;
b.a[i+]+=b.a[i]/inf;
b.a[i]%=inf;
}
while (b.a[b.l]>) b.l++;
}
int main()
{
//读入数据
scanf("%s%s",ch1+,ch2+);
la=strlen(ch1+); lb=strlen(ch2+);
if (la%) a.l=la/+; else a.l=la/;
if (lb%) b.l=lb/+; else b.l=lb/;
for (int i=;i<=a.l;i++){
int k1=max(,la-i*+),k2=la-(i-)*;
for (int j=k1;j<=k2;j++) a.a[i]=a.a[i]*+ch1[j]-'';
}
for (int i=;i<=b.l;i++){
int k1=max(,lb-i*+),k2=lb-(i-)*;
for (int j=k1;j<=k2;j++) b.a[i]=b.a[i]*+ch2[j]-'';
} while (){
if ((a.a[]%==)&&(b.a[]%==)) {
diva();
divb();
cnt++; //这里的cnt是指出现了多少次 a，b都是偶数的情况，在最后的时候再把cnt个2乘回去 （参见最上方算法）
}
else if (a.a[]%==)
diva();
else if (b.a[]%==)
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 ;
}