AcWing 808. 最大公约数
原题链接
中等
C++ 代码
#include <iostream>
#include <numeric> //可以直接使用gcd函数
using namespace std;
//辗转相除法
int gcd1(int a, int b){
if(a < b){
swap(a,b);
}
while(b){
int r = a % b;
a = b;
b = r;
}
return a;
}
//更相减损法
int gcd2(int a, int b){
if(a < b){
swap(a,b);
}
while(a != b){
int d = a - b;
a = max(b,d);
b = min(b,d);
}
return a;
}
//递归法
int gcd3(int a, int b){
if(a < b){
swap(a,b);
}
if(a % b == 0){
return b;
}
return gcd3(b,a % b);
}
int main(){
int a, b;
cin >> a >> b ;
cout << gcd(a,b) << endl;
return 0;
}