一、课上练习

编程练习

1. 求两个自然数M和N的最大公约数：L3071
2. 两个自然数M和N的最小公倍数：L3072
3. 最大公约数和最小公倍数问题：L3073

二、知识总结

✨ 核心思想

欧几里得算法，又称辗转相除法，是一种用来求两个正整数最大公约数（GCD）的古老且高效的算法。该算法基于一个基本的数学原理：两个数的最大公约数不变，即使一个数被另一个数的余数替换之后。

这个算法由古希腊数学家欧几里得在《几何原本》中首次描述，至今已有超过两千年的历史，是已知最古老的算法之一。

✨ 算法原理

欧几里得算法可以描述为以下步骤：

1. 输入两个正整数 a 和 b，且 a >= b。如果 a < b，则交换它们。
2. 求余数：计算 a 除以 b 的余数，即 r = a mod b。
3. 递归或迭代：将 b 和 r 作为新的一对数重复步骤 2，直到余数 r = 0。当 r = 0 时，当前步骤中的除数 b 就是两数的最大公约数。
4. 输出结果：最大公约数 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

✨ 解题步骤详解

遇到求最大公约数或最小公倍数的问题时：

1. 直接求两个数的 GCD：用欧几里得算法即可，递归或迭代均可。递归写法更简洁：gcd(a, b) = (b == 0) ? a : gcd(b, a % b)。
2. 求多个数的 GCD：利用 gcd(a, b, c) = gcd(gcd(a, b), c) 的性质，依次两两求 GCD。
3. 求最小公倍数：先求 GCD，再用公式 lcm = a / gcd * b。
4. 求多个数的 LCM：类似地，lcm(a, b, c) = lcm(lcm(a, b), c)。
5. 不需要保证 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) 需要循环一百万次），实际编程中应该始终使用取模版本。

三、课后练习

编程练习

1. N个数的最大公约数：L3074