|
参考《编程之美》直接利用求余的话 对于特别大的数字计算量还是很大， 利用辗转相减递归速度太慢，所以就用下面的方法 a < b = (b,a) a,b都为偶数 则= 2*(a/2,b/2) a奇数 b偶数 =(a,b/2) a偶数 b奇数 =(a/2,b) a奇数 b奇数 =(a-b,b) |
int gcd(int a,int b){
if(a==b)
return a;
if(a<b){
return gcd(b,a);
}
if(a&1){//a为奇数
if(b&1){
return gcd(a-b,b);
}else{
return gcd(a,b>>1);
}
}else{//a为偶数
if(b&1){
return gcd(a>>1,b);
}else{
return 2*gcd(a>>1,b>>1);
}
}
}
void test1056(){
int a;
int b;
while(std::cin>>a>>b){
std::cout<<gcd(a,b)<<std::endl;
}
}