#创作计划# 辗转相除法
2026-05-11 21:17:49
发布于：广东
萌新的第一个帖子，别说我写的差了
别人随随便便一个帖子直接几十个赞，我这就2赞啊，很搞人心态的，求点赞
本帖禁止刷罐
如果我们想要求两数的最大公因数，平时我们可能是直接暴力，依次枚举进行判断，如下代码：
int a, b, x;
cin >> a >> b;
for(int i = min(a, b);i >= 1;i--)
if(a % i == 0 && b % i == 0){//判断i是否满足
x = i;
break;
}
cout << x << endl;//输出结果
对于一些比较大的数据暴力就 TLE 了，这时候我们就要用辗转相处法
数学思维：对于要求 a和b（ a≥b）的最大公因数辗转相除法步骤：k = b, b = a % b, a = k ……不断重复，直到b = 0时，k就是答案。
因此我们可以写出两种代码（迭代 和 递归）：
1.迭代法
int a, b, k = 0;
cin >> a >> b;
while(b){//若b为0就退出循环
k = b;//由于b要更新，a要用到b，所以用k记录
b = a % b;
a = k;
}
cout << k << endl;
2.递归法
int gcd(int a, int b){
if(b == 0)//若b为0，则最大公因数为a，返回a
return a;
return gcd(b, a % b);//继续求解
}
c++11有__gcd(a, b)可以直接求解!
拓展：我们可以通过求最大公因数来求最小公倍数：a * b / 最大公因数(不懂看最下面)
可以写出代码：
int lcm(int x, int y){
return x * y / __gcd(x, y);
}
在c++17有直接求解最大公因数的函数lcm(a, b)
附件：为什么最小公倍数 = 乘积 / 最大公因数？
令a 最大公因数 * (a / 最大公因数) b 最大公因数 * (b / 最大公因数)
则其最小公倍数 = 最大公因数（公共的，只用乘一次） * (a 最大公因数) * (b 最大公因数) = a b 最大公因数
辗转相除法证明过程：
设 a = q × b + r，其中 q 是 a 除以 b 的商，r 是余数（0 ≤ r < b）。
第一步：证明 gcd(a, b) 是 b 和 r 的公因数
令 d = gcd(a, b)，则 d 能整除 a，也能整除 b。
由 r = a - q × b，因为 d 能整除 a 和 b，所以 d 也能整除 r。
因此 d 是 b 和 r 的公因数，所以 d ≤ gcd(b, r)。
第二步：证明 gcd(b, r) 是 a 和 b 的公因数
令 e = gcd(b, r)，则 e 能整除 b，也能整除 r。
由 a = q × b + r，因为 e 能整除 b 和 r，所以 e 也能整除 a。
因此 e 是 a 和 b 的公因数，所以 e ≤ gcd(a, b)。
由第一步和第二步可得：d = e
即：gcd(a, b) = gcd(b, a mod b)
结论：
反复使用这个等式，每次把较大的数换成它除以较小数的余数，不断重复，直到余数为 0。此时，那个非零的除数就是原来两个数的最大公因数。这就是辗转相除法（欧几里得算法）的原理。
有帮助，赞一个