第 55 章辗转相除——最大公约数与最小公倍数

🏗️ 前情回顾：第 54 章你学会了判断质数、分解质因数、枚举约数，也了解了模运算的基本性质。这些是数论的"工具箱"。现在我们来解决一个非常实际的问题：给你两个数，比如 48 和 18，它们共同的约数有哪些？最大的那个是多少？如果要在程序中高效地求出它——不能一个个试除，有没有更优雅的方法？有——辗转相除法，两千多年前欧几里得发现的算法，至今仍是计算机求 GCD 的标准方式。

🎯 本章目标

学完这一章，你能：

理解最大公约数（GCD）和最小公倍数（LCM）的概念
用辗转相除法（欧几里得算法）高效求 GCD
用 LCM = a / GCD × b 公式求最小公倍数
求三个或更多个数的 GCD / LCM
了解扩展欧几里得算法的基本思想
了解裴蜀定理及其简单应用

📖 故事引入

铺地砖的智慧

小明家要装修客厅。客厅长 48 分米，宽 18 分米。小明爸爸想用正方形地砖铺满整个客厅，并且要求地砖必须是整块使用、不能切割。地砖的边长可以是 1 分米、2 分米、3 分米、6 分米……

为什么偏偏是这几个数？因为它们都能同时整除 48 和 18——或者说，它们是 48 和 18 的公约数。

小明爸爸想用地砖越大越好，这样拼缝少、好看。那应该选多大？当然是选最大的那个公约数——6 分米。

这就是**最大公约数（GCD — Greatest Common Divisor）**的直观含义。

分蛋糕的难题

反过来，小红和小兰分别烤了 12 块和 18 块饼干。她们想把饼干混在一起重新分组，每组里面小红和小兰的饼干配比相同，且每组尽可能大，最多能分几组？

每组配比相同意味着：每组里小红饼干数 ÷ 12 = 小兰饼干数 ÷ 18 = 某个分数。换句话说，组数必须能整除 12 也能整除 18 → 组数必须是公约数。最大组数 = GCD(12, 18) = 6 组。

如果把问题换成"她们分别烤了 a 块和 b 块，想统一用一个大盒子装，每个盒子装相同数量，最少要几个盒子？"——这就引出最小公倍数了。

🧱 知识讲解

55.1 最大公约数：定义与朴素思路

最大公约数（GCD）：能同时整除 a 和 b 的最大正整数。记作 gcd(a, b)。

例如：gcd(48, 18) = 6，gcd(17, 31) = 1（两个质数互质）。

朴素求法：从 min(a, b) 往下枚举，找到第一个能同时整除 a 和 b 的数。但这太慢了——如果 a 和 b 是一亿和两亿，你得试一亿次。

55.2 辗转相除法（欧几里得算法）

这是求 GCD 的最经典算法——核心思想就一行：

gcd(a, b) = gcd(b, a % b)，当 b = 0 时，gcd(a, 0) = a。

为什么？原理不复杂：a 和 b 的公约数集合，与 b 和 (a % b) 的公约数集合，完全相同。

直观理解：设 a > b，那么 a = q×b + r（其中 0 ≤ r < b）。任何能整除 a 和 b 的数 d，也必然能整除 r = a - q×b。反过来说，任何能整除 b 和 r 的数 d，也必然能整除 a = q×b + r。所以 gcd(a, b) = gcd(b, r)。这个 r 就是 a % b。

算法在每次递归中两个参数都在迅速变小，直到 b 变成 0：

cpp

// 递归版——最简洁
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 迭代版——避免递归开销，竞赛常用
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

演练：gcd(48, 18)

a=48, b=18 → b≠0, a=18, b=48%18=12
a=18, b=12 → b≠0, a=12, b=18%12=6
a=12, b=6  → b≠0, a=6,  b=12%6=0
a=6,  b=0  → 返回 6

55.3 辗转相除法的复杂度

每次迭代 a 至少减半（粗略估计），因此复杂度约为 O(log min(a, b))——非常快。即使 a 和 b 是 10¹⁸ 级别，也只迭代约 60 次左右。

💡 这个算法的优雅之处在于：两行代码，O(log n) 的复杂度，两千多年后仍然是计算机科学中求解 GCD 的标准算法。它也是很多高级数论算法的基础。

55.4 最小公倍数（LCM）

最小公倍数（LCM）：能同时被 a 和 b 整除的最小正整数。记作 lcm(a, b)。

关键公式：

LCM(a, b) = a / GCD(a, b) × b

注意：写成 a * b / gcd(a, b) 虽然数学上等价，但在计算机中 a * b 可能溢出 int。所以先除后乘：

cpp

int lcm(int a, int b) {
    return a / gcd(a, b) * b;   // 先除后乘，防溢出
}

演练：LCM(12, 18)

gcd(12, 18) = 6
LCM = 12 / 6 × 18 = 2 × 18 = 36  ✓
（36 能被 12 整除，也 18 整除，且没有更小的了）

55.5 多个数的 GCD 和 LCM

求三个数 a、b、c 的最大公约数：

cpp

int result = gcd(gcd(a, b), c);

多个数的最小公倍数同理：

cpp

int result = lcm(lcm(a, b), c);

这个性质成立是因为 gcd 和 lcm 都有结合律——先算哪两个结果都一样。

55.6 扩展欧几里得算法（入门）

普通辗转相除法告诉我们 gcd(a, b) 等于多少。但它没有告诉我们另外一件事：

是否存在整数 x 和 y，使得 ax + by = gcd(a, b) ？

答案是：一定存在。而且可以在辗转相除的过程中顺便把 x 和 y 算出来——这就是扩展欧几里得算法。

例如：a = 48, b = 18，gcd = 6。确实存在 48×(-1) + 18×3 = -48 + 54 = 6。这里 x = -1, y = 3。

cpp

// 扩展欧几里得：返回 gcd，同时通过引用参数返回 x 和 y
int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);  // 注意参数顺序！
    y -= a / b * x;
    return d;
}

这个算法在求解模逆元（密码学核心操作）和一次不定方程中有重要应用。现阶段不要求完全掌握推导，先记住"它能做这件事"即可——下一册会在加密和数论进阶中重新出场。

55.7 裴蜀定理（Bézout's identity）

扩展欧几里得算法的理论基础是裴蜀定理：

对于任意整数 a、b，存在整数 x、y 使得 ax + by = gcd(a, b)。而且 ax + by 能表示的所有正整数恰好是 gcd(a, b) 的所有倍数。

推论：方程 ax + by = c 有整数解，当且仅当 gcd(a, b) 整除 c。

例如：3x + 5y = 1 有整数解吗？gcd(3, 5) = 1，1 整除 1 → 有解。实际上 x=2, y=-1 就是一组解（3×2 + 5×(-1) = 1）。

3x + 6y = 4 有整数解吗？gcd(3, 6) = 3，3 不整除 4 → 无解。想想也对，左边一定是 3 的倍数，右边是 4，不可能相等。

✋ 动手试试

试试 1：写辗转相除法的迭代版和递归版，输入两个正整数，输出它们的 GCD。对 (48, 18)、(100, 25)、(17, 31) 分别测试。

试试 2：写 LCM 函数，测试 (12, 18) → 36，(7, 13) → 91，(100, 25) → 100。

试试 3：输入三个正整数 a、b、c，输出它们的 GCD 和 LCM。

试试 4（探索）：写一个程序暴力验证"gcd(a, b) × lcm(a, b) = a × b"这一等式——随机生成 1000 对 (a, b)，逐一验证。

⚠️ 容易犯的错

错 1：GCD 中用 a % b 写在 a 更新之前

❌

cpp

while (b != 0) {
    a = b;
    b = a % b;  // 此时 a 已经是新的 b 了！错误！
}

✅ 先保存旧的 b，或同时交换：

cpp

while (b != 0) {
    int t = b;
    b = a % b;
    a = t;
}

错 2：LCM 先乘后除导致溢出

❌ return a * b / gcd(a, b); // a*b 可能溢出

✅ return a / gcd(a, b) * b; // 先除后乘，安全

错 3：GCD 忘考虑 0 的情况

❌ 如果不处理 b == 0 的情况，递归会死循环或除零错误

✅ GCC 的边界条件：if (b == 0) return a;

错 4：把 GCD / LCM 当成只适用于正整数

❌ 传入负数 → 结果可能不正确

✅ 求 GCD 之前先取绝对值：a = abs(a); b = abs(b);

📝 练习

基础题

1. 填空题

（1）辗转相除法的核心递推关系是：gcd(a, b) = gcd(____, ____)，当 b ≠ 0。

（2）递归终止条件是 b == ____ 时，返回 ____。

（3）LCM(a, b) = ____ / GCD(a, b) × ____。

（4）如果 gcd(a, b) = 1，则称 a 和 b ____。

2. 读代码写结果

cpp

int func(int a, int b) {
    while (b) { int t = b; b = a % b; a = t; }
    return a;
}

求 func(36, 24) 和 func(17, 13) 的返回值。

提高题

3. 编程题 — 最简分数

输入分子 a 和分母 b（保证 b > 0），输出这个分数的最简形式。例如输入 24/36，输出 2/3。（提示：分子分母同时除以它们的 GCD。）

4. 编程题 — 最大公约数序列

输入 N 和 M（N ≤ M ≤ 10⁵），统计在 [N, M] 范围内有多少对 (i, j)（i < j）满足 gcd(i, j) = 1（即互质）。

（提示：如果用双重循环 O((M-N)²) 会超时。想想欧拉函数的思路，或者用更高效的方法。本题可以用暴力思路通过 N 和 M 差值较小的情况。）

挑战题

5. 编程题 — 线性丢番图方程

用扩展欧几里得算法求解方程 ax + by = c。输入 a、b、c，判断是否有整数解，如果有则输出任意一组解 (x, y)。

输入：48 18 6
输出：有解，一组解为 x=-1, y=3
      （验证：48×(-1) + 18×3 = 6 ✓）

输入：3 6 4
输出：无解

6. 编程题 — 最小公倍数的循环节

给定正整数 N，求最小的正整数 K，使得 K 能被 1, 2, 3, …, N 中每一个数整除。换句话说，K = LCM(1, 2, 3, …, N)。

输入：5
输出：60      （因为 LCM(1,2,3,4,5) = 60）

（提示：不需要对每个数求 LCM。核心在于：对于每个质数 p，找到 N 以内 p 的最高次幂 p^e ≤ N，最后把这些 p^e 乘起来。）

🧠 本章小结

GCD（最大公约数）：
    辗转相除法：while (b) { t=b; b=a%b; a=t; }
    递归版：return b==0 ? a : gcd(b, a%b);
    复杂度：O(log min(a,b))

LCM（最小公倍数）：
    lcm(a,b) = a / gcd(a,b) * b  （先除后乘防溢出）
    多个数：lcm(a, lcm(b, c))

扩展欧几里得（入门）：
    求 ax + by = gcd(a,b) 的一组整数解
    函数原型：int exgcd(int a, int b, int& x, int& y)

裴蜀定理：
    ax + by = c 有整数解 ⇔ gcd(a,b) | c

📝 配套练习

共7题。gcd从基本→约分→裴蜀定理→多公约数→推理，每题一种应用场景。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1029	https://hydro.ac/p/luogu-P1029	gcd+lcm、枚举公式
◆ 拓展	luogu-P1888	https://hydro.ac/p/luogu-P1888	gcd、最简分数约分
◆ 拓展	luogu-P4549	https://hydro.ac/p/luogu-P4549	裴蜀定理、gcd
◆ 拓展	luogu-P1414	https://hydro.ac/p/luogu-P1414	gcd、多个数的公约数
◆ 拓展	luogu-P1072	https://hydro.ac/p/luogu-P1072	gcd、LCM推理解
◆ 拓展	luogu-P1572	https://hydro.ac/p/luogu-P1572	gcd、分数加法约分
◆ 拓展	luogu-P2118	https://hydro.ac/p/luogu-P2118	gcd、比例化简、枚举

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节。

配套练习

共7题。gcd从基本→约分→裴蜀定理→多公约数→推理，每题一种应用场景。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1029	https://hydro.ac/p/luogu-P1029	gcd+lcm、枚举公式
◆ 拓展	luogu-P1888	https://hydro.ac/p/luogu-P1888	gcd、最简分数约分
◆ 拓展	luogu-P4549	https://hydro.ac/p/luogu-P4549	裴蜀定理、gcd
◆ 拓展	luogu-P1414	https://hydro.ac/p/luogu-P1414	gcd、多个数的公约数
◆ 拓展	luogu-P1072	https://hydro.ac/p/luogu-P1072	gcd、LCM推理解
◆ 拓展	luogu-P1572	https://hydro.ac/p/luogu-P1572	gcd、分数加法约分
◆ 拓展	luogu-P2118	https://hydro.ac/p/luogu-P2118	gcd、比例化简、枚举

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我能用迭代和递归两种方式写出 GCD
[ ] 我理解辗转相除为什么成立（公约数集合不变）
[ ] 我会用 LCM 公式并注意先除后乘
[ ] 我能求三个或更多个数的 GCD 和 LCM
[ ] 我了解扩展欧几里得算法能做什么
[ ] 我能用裴蜀定理判断 ax+by=c 是否有整数解

🚀 下章预告

GCD 和 LCM 帮你处理了"两个数之间的关系"。但还有一个非常接地气的问题：给你 N 个不同的选项，从中选 M 个——有多少种选法？这不是简单的加减乘除，涉及到一个全新的领域——排列组合。下一章我们打开这扇门，看看杨辉三角、阶乘、组合数这些"计算可能性"的工具。

第 55 章 辗转相除——最大公约数与最小公倍数 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

55.1 最大公约数：定义与朴素思路 ​

55.2 辗转相除法（欧几里得算法） ​

55.3 辗转相除法的复杂度 ​

55.4 最小公倍数（LCM） ​

55.5 多个数的 GCD 和 LCM ​

55.6 扩展欧几里得算法（入门） ​

55.7 裴蜀定理（Bézout's identity） ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：GCD 中用 a % b 写在 a 更新之前 ​

错 2：LCM 先乘后除导致溢出 ​

错 3：GCD 忘考虑 0 的情况 ​

错 4：把 GCD / LCM 当成只适用于正整数 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​

🚀 下章预告 ​