求两个数的最大公约数（最小公倍数）
最大公约数×最小公倍数=两数相乘
最小公倍数=两数相乘/最大公阿约数
1.辗转相除法（欧几里得算法）
依据定理两个整数的最大公约数等于较小数和两数取模的最大公约数
时间复杂度O（log(n)）
#include
#include
using namespace std;
int main()
{
int a, b,ans;
cin >> a >> b;
int x, y;
x = max(a, b);
y = min(a, b);
//x永远放小的数，y永远放大的数
while (true)
{
if (x % y == 0)
{
ans = y; break;
}
else
{
int tem = x % y;
x = y;
y = tem;
}
}
cout << ans << endl;
return 0;
}
2.辗转相减法/更相减损法
时间复杂度O（log（max(a,b)）
#include
#include
using namespace std;
int main()
{
int a, b, ans, x, y;
cin >> a >> b;
x = a; y = b;
while (true)
{
if (a > b)
a = a - b;
else if (a < b)
b = b - a;
else if (a == b)
{
ans = a;
break;
}
}
cout << ans << endl;
return 0;
}
3.暴力遍历
#include
#include
using namespace std;
int main()
{
int a, b, ans;
cin >> a >> b;
for (int i = min(a, b); i > 0; i--)
{
if (a % i == 0 && b % i == 0)
{
ans = i; break;
}
}
cout < return 0; } 4。函数递归 #include #include using namespace std; int gcd(int x,int y) { while (true) { if (x % y == 0) return y; else return gcd(y, x % y); } } int main() { int a, b; cin >> a >> b; int x = max(a, b); int y = min(a, b); int ans = gcd(x, y); cout < return 0; }