猫史档案馆

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
	if(a==b)return a;
	if((a&1)==0&&(b&1)==0){
		return gcd(a>>1,b>>1)<<1;
	}
	else if((a&1)==0&&(b&1)!=0){
		return gcd(a>>1,b);
	}
	else if((a&1)!=0&&(b&1)==0){
		return gcd(a,b>>1);
	}
	else{
		int b=max(a,b);
		int s=min(a,b);
		return gcd(b-s,s);
	}
}
int main(){
	cout<<gcd(74,111)<<endl;
	cout<<gcd(114,514)<<endl;
	cout<<gcd(314,628)<<endl;
	cout<<gcd(81,123)<<endl;
    return 0;
}

此方法位更相减损法与移位结合

时间复杂度为O(log(max(a,b)))

比辗转相除法快，究其原因是：避免了取模运算