新人第一次发帖,有什么错误请指教
#include<iostream>
using namespace std;
int gcd(int a,int b){
if(a==b)return a;
if(a<b)return gcd(b,a);//保证A永远大于B
else {
//和1做位与运算,判断奇偶
if(!a&1&&!b&1)return gcd(a>>1,b>>1)<<1;//如果AB都为偶数时,则同时除2再进行运算
if(!a&1&&b&1)return gcd(a>>1,b);//当奇偶不同时,再将偶数除2进行运算
if(a&1&&!b&1)return gcd(a,b>>1);
else return gcd(b,a-b);//用更像减损法得到偶数再进行运算直到求出最大公约数
}
}
int main(){
int a,b;
cin>>a>>b;
printf("%d",gcd(a,b));
return 0;
}
这做法骚啊。但这个做法是怎么保证时间复杂度的呢?
把更相减损法和辗转相除法结合,避免因两数相差过大减损次数过多和两数过大取模效率过低,对于位运算的话运行速度快,有利于提高运算效率。