最大公约数

一句话算法

辗转相除法不断把“大问题”换成“除数和余数”的小问题，直到余数为 $0$，最后的非零数就是最大公约数。

问题模型

给定两个整数 $a,b$，要求它们的最大公约数：

最大公约数是同时整除 $a$ 和 $b$ 的最大正整数。例如：

因为 $4 \mid 44$ 且 $4 \mid 12$，并且没有比 $4$ 更大的正整数能同时整除它们。

朴素做法可以从 $\min(a,b)$ 开始向下枚举因子，但最坏需要 $O(\min(a,b))$。欧几里得算法利用余数不断缩小问题，复杂度接近对数级。

核心直觉

设：

这里 $r$ 是 $a$ 除以 $b$ 的余数。

如果一个数 $d$ 能同时整除 $a$ 和 $b$，那么它也一定能整除：

也就是说，$a$ 和 $b$ 的共同因子，不会因为把 $a$ 换成 $r$ 而改变。

所以：

这就是欧几里得算法的核心。

算法步骤

1. 若 $b=0$，答案就是 $|a|$。
2. 否则计算余数 $r=a\bmod b$。
3. 把问题从 $\gcd(a,b)$ 变成 $\gcd(b,r)$。
4. 重复上述过程，直到第二个数变成 $0$。

以 $\gcd(44,12)$ 为例：

算法证明

核心不变量：每一步替换后，两个数的所有公因子集合不变。

设：

其中 $q$ 是整数，$r=a\bmod b$。

1. 从左到右

   若 $d \mid a$ 且 $d \mid b$，则：

   $$d \mid (a-qb)$$

   又因为 $a-qb=r$，所以：

   $$d \mid r$$

   因此 $d$ 也是 $b,r$ 的公因子。

2. 从右到左

   若 $d \mid b$ 且 $d \mid r$，则：

   $$d \mid (qb+r)$$

   又因为 $qb+r=a$，所以：

   $$d \mid a$$

   因此 $d$ 也是 $a,b$ 的公因子。

3. 结论

   $a,b$ 的公因子集合和 $b,r$ 的公因子集合完全相同，所以最大公约数也相同：

   $$\gcd(a,b)=\gcd(b,a\bmod b)$$

每次取余后第二个数严格变小，过程一定会结束。结束时 $\gcd(x,0)=|x|$，所以算法正确。

复杂度分析

• 时间复杂度：$O(\log \min(a,b))$。
• 空间复杂度：迭代写法为 $O(1)$。

若使用递归写法，递归栈空间为 $O(\log \min(a,b))$。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

        #include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << "\n";
    return 0;
}
    

测试用例

输入：

44 12

输出：

4

过程：

44 % 12 = 8
12 % 8 = 4
8 % 4 = 0

所以答案是 4。

再看一个互质例子：

35 64

输出：

1

应用分类详解

最大公约数的本质是：找两个整数共同拥有的最大“整除单位”。凡是题目里出现“约分、整除、周期同步、比例化简、线性组合”等信号，都应该想到 gcd。

一、分数约分与比例化简

典型模式： 需要把两个整数的比例化成最简形式。

识别信号： 题面出现“最简分数”“斜率比较”“比例相同”“方向向量去重”。

核心建模： 用 $g=\gcd(|a|,|b|)$，把 $(a,b)$ 变成 $(a/g,b/g)$。

二、整除结构与数论基础

典型模式： 问两个数是否有公共因子，或需要用互质性质推出结论。

识别信号： 题面出现“互质”“约数”“倍数”“整除”“最大公因数”。

核心建模： 若 $\gcd(a,b)=1$，则 $a,b$ 没有公共质因子，可以使用互质相关性质。

三、最小公倍数与周期同步

典型模式： 两个周期什么时候再次同时发生。

识别信号： 题面出现“周期”“同时出现”“下一次相遇”“最小公倍数”。

核心建模： 先求 gcd，再用：

四、扩展欧几里得的入口

典型模式： 要求解整数方程 $ax+by=c$。

识别信号： 题面出现“不定方程”“线性组合”“模逆元”“同余方程”。

核心建模： 方程 $ax+by=c$ 有整数解，当且仅当 $\gcd(a,b)\mid c$。扩展欧几里得在 gcd 的递归结构上继续回代系数。

经典例题

1. luogu-P1888

给出三个数，按要求输出最简比例。核心操作是排序后取分子分母，再用 gcd 约分。

2. luogu-P1029

已知两个数的 gcd 和 lcm，反推满足条件的数对。利用 $ab=\gcd(a,b)\times\operatorname{lcm}(a,b)$ 缩小搜索空间。

3. luogu-P1082

求乘法逆元，是扩展欧几里得的模板题。普通 gcd 给出递归骨架，exgcd 在这个骨架上回代出系数。

参考

• 旧版文章：Rbook_ejs_old/book/math/numberTheory/gcd/index.md