本课时有配套视频讲解，购买后即可观看（永久有效）
欧几里得算法
一、课上练习
编程练习
二、知识总结
✨ 核心思想
欧几里得算法，又称辗转相除法，是一种用来求两个正整数最大公约数（GCD）的古老且高效的算法。该算法基于一个基本的数学原理：两个数的最大公约数不变，即使一个数被另一个数的余数替换之后。
这个算法由古希腊数学家欧几里得在《几何原本》中首次描述，至今已有超过两千年的历史，是已知最古老的算法之一。
✨ 算法原理
欧几里得算法可以描述为以下步骤：
- 输入两个正整数 a 和 b，且 a >= b。如果 a < b，则交换它们。
- 求余数：计算 a 除以 b 的余数，即 r = a mod b。
- 递归或迭代：将 b 和 r 作为新的一对数重复步骤 2，直到余数 r = 0。当 r = 0 时，当前步骤中的除数 b 就是两数的最大公约数。
- 输出结果：最大公约数 b。
以下是使用递归方式实现的欧几里得算法：
欧几里得算法代码示例
1#include<iostream>
2using namespace std;
3
4int gcd(int a, int b) {
5 if (b == 0) {
6 return a;
7 }
8 return gcd(b, a % b);
9}
10
11int main() {
12 int n = 0;
13 int m = 0;
14 while (true) {
15 cin >> n >> m;
16 cout << gcd(n, m) << endl;
17 }
18 return 0;
19}✨ 执行示例
假设需要计算 252 和 105 的最大公约数：
- 第一步：计算 252 / 105 = 2，余数 42，即 252 mod 105 = 42
- 第二步：计算 105 / 42 = 2，余数 21，即 105 mod 42 = 21
- 第三步：计算 42 / 21 = 2，余数 0，即 42 mod 21 = 0
余数为 0，此时除数为 21，因此最大公约数是 21。
执行示例： 以计算 gcd(462, 180) 为例，展示递归调用过程：
1gcd(462, 180)
2 → b=180 ≠ 0，计算 462 % 180 = 102
3 → 调用 gcd(180, 102)
4 → b=102 ≠ 0，计算 180 % 102 = 78
5 → 调用 gcd(102, 78)
6 → b=78 ≠ 0，计算 102 % 78 = 24
7 → 调用 gcd(78, 24)
8 → b=24 ≠ 0，计算 78 % 24 = 6
9 → 调用 gcd(24, 6)
10 → b=6 ≠ 0，计算 24 % 6 = 0
11 → 调用 gcd(6, 0)
12 → b=0，返回 a=6
13 → 返回 6
14 → 返回 6
15 → 返回 6
16 → 返回 6
17 → 返回 6最终结果：gcd(462, 180) = 6
验证：462 = 6×77，180 = 6×30，而 gcd(77, 30) = 1，所以 6 确实是最大公约数。
✨ 算法评价
欧几里得算法是高效的，特别适用于大数的最大公约数计算。它的时间复杂度大约是 O(log(min(a, b)))，这使得即使对于非常大的数字，算法也能迅速收敛到结果。这种对数级别的复杂度来源于每次取模操作至少会将较大的数减半。
✨ 利用 GCD 求最小公倍数（LCM）
两个数 a 和 b 的最小公倍数公式为：lcm(a, b) = a / gcd(a, b) * b
注意先除后乘可以避免中间结果溢出。例如：
- lcm(462, 180) = 462 / 6 × 180 = 77 × 180 = 13860
✨ 解题步骤详解
遇到求最大公约数或最小公倍数的问题时：
- 直接求两个数的 GCD：用欧几里得算法即可，递归或迭代均可。递归写法更简洁：
gcd(a, b) = (b == 0) ? a : gcd(b, a % b)。 - 求多个数的 GCD：利用
gcd(a, b, c) = gcd(gcd(a, b), c)的性质，依次两两求 GCD。 - 求最小公倍数：先求 GCD，再用公式
lcm = a / gcd * b。 - 求多个数的 LCM：类似地，
lcm(a, b, c) = lcm(lcm(a, b), c)。 - 不需要保证 a > b：欧几里得算法即使传入 a < b，第一步
a % b = a，下一步自动变成gcd(b, a)，相当于自动交换了。
✨ 常见错误
- 递归终止条件写错：应该是
b == 0时返回a，而不是a == 0时返回b（虽然数学上等价，但与代码中的参数顺序要一致）。 - 求 LCM 时先乘后除导致溢出：
a b / gcd(a, b)中a b可能超出int甚至long long的范围。应该写成a / gcd(a, b) * b，先除后乘。 - 忘记处理输入为 0 的情况：gcd(0, n) = n，gcd(0, 0) 在数学上未定义，但通常约定为 0。如果题目保证输入为正整数则无需担心。
- 用减法代替取模：有些教材介绍"辗转相减法"，即用
a - b代替a % b，虽然正确但效率极低（想象 gcd(1000000, 1) 需要循环一百万次），实际编程中应该始终使用取模版本。
三、课后练习
编程练习
- N个数的最大公约数：L3074