Stein算法是更相减损术的改进。
求gcd(a,b)时，可以分为几种情况进行优化。
1. a和b都是偶数。gcd(a,b)=2*gcd(a/2,b/2)
2. a b一奇一偶(不妨a奇b偶)。gcd(a,b)=gcd(a,b/2)
3. a和b都是奇数。gcd(a,b)=gcd((a+b)/2,(a-b)/2)
结束条件 gcd(a,a)=a
Stein算法只用到加减法和移位
#include<bits/stdc++.h>
using namespace std;
int stein_gcd(int a,int b) //递归形式
{
if(a<b)
a^=b,b^=a,a^=b;
if(b==0)
return a;
if((!(a&1))&&(!(b&1)))
return stein_gcd(a>>1,b>>1)<<1;
else if((a&1)&&(!(b&1)))
return stein_gcd(a,b>>1);
else if((!(a&1)&&(b&1)))
return stein_gcd(a>>1,b);
else
return stein_gcd(a-b,b);
}
int stein(int a,int b) //循环形式
{
int k=1; //k用来记录2的次幂
while((!(a&1))&&(!(b&1)))
{
k<<=1;
a>>=1;
b>>=1;
}
while(!(a&1))
a>>=1;
while(!(b&1))
b>>=1;
if(a<b)
a^=b,b^=a,a^=b;
while(a!=b)
{
a-=b;
if(a<b)
a^=b,b^=a,a^=b;
}
return k*a;
}