← 目录 / 算法文档 · 模块一 数学基础 / 1.4 最大公约数

1.4　最大公约数

从枚举到欧几里得算法（辗转相除法）——求两个数最大公约数最经典的优化之路。

本页目录
① 什么是最大公约数

两个整数的公约数，是指能同时整除这两个数的正整数；在所有公约数里最大的那一个，就叫做最大公约数（Greatest Common Divisor，简称 GCD）。比如 12 和 18，先列出各自的因数，再看看哪些是两边都有的：

12 和 18 的因数集合 —— 重叠部分就是公约数
12 的因数
1
2
3
4
6
12
18 的因数
1
2
3
6
9
18
公约数
1
2
3
6
绿色格子是两边都有的因数（公约数）：1、2、3、6，其中带描边的 6 是最大的一个——所以 GCD(12, 18) = 6。蓝色、粉色格子分别是只属于 12、只属于 18 的因数，不是公约数。
💡
互质：如果两个数的最大公约数是 1（也就是除了 1 之外没有其他公约数），就说这两个数互质。比如 GCD(8, 15) = 1，8 和 15 互质——注意互质不要求两个数本身是质数，8 和 15 都是合数，但它们互相之间没有除 1 以外的公共因数。
② 基础写法：枚举法

最直接的想法：从两个数里较小的那个开始，往下一个个试，第一个能同时整除两个数的，就是最大公约数——因为是从大到小找的，找到的第一个必然是最大的：

C++ · 枚举法求最大公约数
1int Gcd(int a, int b)
2{
3 int smaller = min(a, b);
4 for (int i = smaller; i >= 1; i--)
5 {
6 if (a % i == 0 && b % i == 0)
7 {
8 return i; // 从大到小找，第一个找到的就是最大公约数
9 }
10 }
11 return 1; // 理论上不会执行到这里，i=1 总能同时整除任何数
12}

这种写法最坏情况下要从 min(a, b) 一直试到 1，时间复杂度是 O(min(a, b))——当两个数很大、而最大公约数又很小的时候（比如两个几乎互质的大数），这个循环会跑很多很多次。

③ 优化：欧几里得算法

这里有一个非常巧妙的发现，叫欧几里得算法（也叫辗转相除法），可以完全不用枚举，飞快地算出最大公约数。理解它最简单的方式，不是看公式，而是想象铺地砖。

假设有一块长方形的地板，两条边分别是 a 和 b，想用同样大小的正方形方砖把它刚好铺满——不能切割方砖，不能留缝，也不能重叠。能完成这件事的最大方砖边长，正好就是 a 和 b 的最大公约数：因为方砖边长必须同时能整除 a 和 b（横着摆整数块、竖着摆整数块都要刚好对齐），而我们要的就是这样的边长里最大的一个。

💡
怎么找到这个最大边长，而不用一个个去试？用较短的那条边当方砖边长，沿着长边铺过去，能铺几块整的就铺几块——剩下铺不满的那一窄条，就当成一块"新地板"。再对这块新地板重复同样的操作：用它较短的那条边当方砖边长，继续铺、继续剩。一直这样做下去，地板会越铺越小，直到有一次正好铺满、一点都不剩——这时候用的方砖边长，就是答案。
铺地砖求 GCD(48, 18) —— 跟着图走一遍，不用写任何公式
第 1 轮：地板是 48 × 18，用较短边 18 当方砖边长去铺
铺了 2 块 18×18 的方砖，剩下一条 12 × 18 的窄地板还没铺满
第 2 轮：新地板是 18 × 12，用较短边 12 当方砖边长去铺
铺了 1 块 12×12 的方砖，剩下一条 6 × 12 的窄地板还没铺满
第 3 轮：新地板是 12 × 6，用较短边 6 当方砖边长去铺
铺了 2 块 6×6 的方砖，正好铺满，一点都不剩！
最后这一块方砖的边长是 6——铺满了 12×6 这块地板，没有任何剩余，所以 GCD(48, 18) = 6，和第①节用因数列出来的答案完全一致。
📌
为什么"换一块新地板继续铺"答案不会变？注意第 1 轮的大地板，其实正好是"2 块 18×18 的方砖"加上"1 条 12×18 的窄地板"拼起来的。如果一块方砖能铺满整个大地板，那它必须也能铺满这两块 18×18 的正方形——既然能铺满正方形，剩下那条窄地板自然也必须能被同样大小的方砖铺满。反过来想同样成立：只要一块方砖能铺满 18×18 的正方形、又能铺满剩下的窄地板，那它就一定能铺满整个大地板。所以，"铺满大地板的最大方砖"和"铺满剩下这条窄地板的最大方砖"，其实是同一个问题，答案必然相同。

把"铺方砖、量剩下多窄"这件事翻译成数字：每一轮"能铺几块整的"，就是除法的商；"剩下多窄的一条"，就是除法的余数，也就是代码里的 a % b。整个铺地砖的过程，换成数字来写是这样的：

GCD(48, 18) 的欧几里得算法执行过程
aba % b（新余数）
48÷18余12
18÷12余6
12÷6余0
余数变成 0，此时的 b = 6 —— GCD(48, 18) = 6
这张表里的每一行，正好对应上面铺地砖每一轮的"铺了几块、剩下多少"——只是不画方块，直接写数字。
C++ · 欧几里得算法（循环写法）
1int Gcd(int a, int b)
2{
3 while (b != 0)
4 {
5 int remainder = a % b;
6 a = b;
7 b = remainder;
8 }
9 return a; // b 变成 0 时，a 就是最大公约数
10}

每一轮循环：先算出余数 remainder = a % b，然后把 b 挪到 a 的位置，把余数挪到 b 的位置——对应的就是"用 (b, a%b) 代替 (a, b)"。当 b 变成 0 时，说明上一轮的 a 已经能被上一轮的 b 整除，循环结束，此时的 a 就是最终答案。

🎯
欧几里得算法的时间复杂度是 O(log(min(a, b)))——每经过两轮，较小的数至少会减半，所以即使 a、b 是非常大的数（比如几十亿），通常也只需要循环几十次就能算出答案，比枚举法快得不是一个量级。
递归写法：和铺地砖、循环版本是同一件事

GCD(a, b) = GCD(b, a % b) 这个关系——"求大问题"转化成"求一个更小的同类型问题"——正是递归最典型的应用场景。前面铺地砖的每一轮、循环版本的每一次循环，本质上都是在做同一件事：用新的一组 (a, b) 代替旧的一组。用递归来写，可以让这种"自己调用自己、问题越变越小"的结构直接体现在代码里：

C++ · 欧几里得算法（递归写法）
1int Gcd(int a, int b)
2{
3 if (b == 0) return a; // 递归出口：地板正好铺满，a 就是答案
4 if (a % b == 0) return b; // a 正好能被 b 整除，b 自己就是答案
5 return Gcd(b, a % b); // 否则换成剩下那条窄地板，继续铺
6}

第 3 行是递归出口：地板正好铺满（b == 0），a 就是答案。第 4 行是一个小判断：如果 a 正好能被 b 整除，说明 b 自己就已经是最大公约数了，不用再往下多调用一层去确认。剩下第 5 行才是真正的"递归"——换成剩下那条窄地板，继续铺。用 Gcd(48, 18) 走一遍：

Gcd(48, 18) 的递归调用链
Gcd(48, 18)
48%18≠0，调用
↓
Gcd(18, 12)
18%12≠0，调用
↓
Gcd(12, 6)
12 % 6 == 0 —— 直接返回 b = 6，这个结果会一路向上传回去，Gcd(48, 18) 最终的结果也是 6
💡
循环和递归，本质是同一个过程的两种写法：循环版本里，每一轮用变量重新赋值（a = b; b = remainder;）来"前进到下一轮"；递归版本里，每一层用一次新的函数调用来"前进到下一轮"——两者经历的中间结果完全对应，只是"记住当前进度"的方式不同：循环靠变量覆盖，递归靠每一层调用自带的参数。两种写法都正确，竞赛代码里因为递归版本更简短，会更常见一些。
④ 完整代码与对比

用 GCD(360, 48) 实际数一数两种写法的检查/计算次数，差距非常明显：

求 GCD(360, 48) —— 两种写法的步骤数对比
枚举法
25 次
欧几里得算法
2 步
枚举法要从 48 往下试到 24 才能找到答案，一共检查了 25 次；欧几里得算法只需要两步：360 % 48 = 24，48 % 24 = 0，立刻得到 GCD(360, 48) = 24。
写法核心思路时间复杂度说明
枚举法从 min(a,b) 往下逐个试除O(min(a, b))直观但慢，数字大时容易超时
欧几里得算法GCD(a,b) = GCD(b, a%b)，不断缩小问题规模O(log(min(a, b)))竞赛标准写法，必须掌握
💡
标准库里也有现成的：C++17 开始，标准库 <numeric> 头文件直接提供了 std::gcd(a, b) 函数，效果和这里手写的一样。但不少在线评测系统使用的编译器版本较旧，不一定支持 C++17，所以掌握手写欧几里得算法依然是基本功——既保证任何环境都能用，也是很多更复杂算法（比如下一节的最小公倍数、还有数论里的扩展欧几里得）的基础。