#创作计划# 辗转相除大法
2026-01-03 13:17:36
发布于：广东
9阅读
0回复
0点赞
如果我们想要求两数的最大公因数，平时我们可能是直接暴力，依次枚举进行判断，如下代码：
int a, b, x;
cin >> a >> b;
for(int i = min(a, b);i >= 1;i--)
if(a % i == 0 && b % i == 0){
x = i;
break;
}
cout << x << endl;
对于一些比较大的数据暴力就TLE了，这时候我们就要用辗转相处法：
对于要求 a和b(ab）的最大公因数辗转相除法步骤：k b, b a b, a $= $k ……不断重复，直到b 0时，k就是答案。
因此我们可以写出两种代码（迭代和递归）：
1.迭代
int a, b, k = 0;
cin >> a >> b;
while(b){
k = b;
b = a % b;
a = k;
}
cout << k << endl;
2.递归
int gcd(int a, int b){
if(b == 0)
return a;
return gcd(b, a % b);
}
如果说不想手写gcd? 那么c++11直接有一个__gcd(a, b)可以直接求解!
拓展：我们可以通过求最大公因数来求最小公倍数：$a * b ÷ $ 最大公因数
可以写出代码：
int lcm(int x, int y){
return x * y / __gcd(x, y);
}
当然，如果还是想偷懒c++17有一个直接求解的函数lcm(a, b)
如果觉得本帖对你有所帮助，就点个赞吧
这里空空如也
有帮助，赞一个