Sengxian's Blog

欧几里德算法非常简洁，明了，通俗易懂。

$m(m > 0)$ 整除 $n$ 记作 $m \vert n$，其定义为存在一个整数 $k$ 使得 $km = n$。

欧几里德算法

两个数 $a$ 和 $b$ 的最大公因子（greatest common divisior）是能整除它们两者的最大整数。欧几里德算法（又称辗转相除法）用于计算两个整数 $a$，$b$ 的最大因子。我们记 $\gcd(a,b)$ 为自然数 $a$ 与 $b$ 的最大公因子。特别的，有 $\gcd(0, n) = 0$，因为任何整数都能整除 $0$。

内容

证明

首先考虑边界情况，因为 $\gcd(0, n) = n$，所以这个边界显然是正确的。

接着考虑一般情况，设 $a$ 除以 $b$ 得到的商为 $p$ 余数为 $q$，则有

考虑 $\gcd(b, q)$ ，两个可以被 $\gcd(b, q)$ 整除的数相加得到 $a$，可知 $a$ 一定可以被 $\gcd(b, q)$ 整除。所以 $\gcd(b, q)$ 既能整除 $a$ 又能整除 $b$。因为 $\gcd(b, q)$ 同时整除 $a, b, q$ ，所以 $\gcd(b, q)$ 也能整除 $\gcd(a, b)$。这就说明

变化一下之前的式子

同理可得 $\gcd(a, b)$ 同时整除 $a, b, q$，所以有

结合两个式子，就能得证

上面的推导，都是基于 $a \ge b$ 的，那么要是 ，怎么办呢？不用担心，其实它一步就会变成 $\gcd(b, a)$。

复杂度

接下来我们估算欧几里德算法的复杂度。我们不妨设 $a > b$。分两种情况考虑：

1. 若 $b > \frac a 2$，那么 $a\bmod b = a - b < \frac a 2$
2. 若 $b \le \frac a 2$，那么 $a\bmod b < b < \frac a 2$

因此经过至多 2 次递归之后，第二个参数要小于原来的一半。所以其复杂度为 $O(\log\max(a, b))$，足以证明欧几里德算法是非常高效的了。

扩展欧几里德算法

用途

扩展欧几里德算法是对欧几里德算法的扩展，它可以用来求解形如 $ax + by = c(a, b, c \in Z)$ 的方程的一组整数解。

方程解的讨论

事实上，只有当 $\gcd(a, b)\mid c$ 时，此方程才有整数解，下面简短给出证明：

同时除以 $\gcd(a, b)$

方程左边的系数显然还是整数，所以方程右边必然要为整数，方程才可能有解。可见只有当 $\gcd(a, b)\mid c$ 时，此方程才有整数解。

实现

那么如何实现扩展欧几里德算法呢，我们从欧几里德算法给我们提供的等式来入手。

我们记 $\mathrm{exgcd}(a, b, x, y)$ 为求解方程 $ax + by = \gcd(a, b)$ 的函数，其中形式参数 $x, y$ 均为引用类型。

一样先考虑边界情况，当 $b = 0$ 时，原方程可化为 $ax = \gcd(a, 0)$，解得 $\begin{cases} x = 1 \\y = 0 \end{cases}$ 。

对于一般情况，设 $a' = b, b' = a\bmod b$，则考虑方程

以及我们要求解的方程

有恒等式 $\gcd(a, b) = \gcd(b, a\bmod b)$，所以

整理得到

其中 $x',y'$ 为方程 $a'x' + b'y' = \gcd(a', b')$ 的解。我们比对两个方程的系数，发现我们只要求出了 $x'$ 和 $y'$，我们就能求出 $x$ 以及 $y$，它们对应的关系为

由此我们成功得到递归式以及边界条件，可以求解方程了，每次只需要递归 $\mathrm{exgcd}(b, a\bmod b, x, y)$，然后处理一下即可得到方程 $ax + by = \gcd(a, b)$ 的一组解。

对于求解方程 $ax + by = c(\gcd(a, b)\mid c)$，只需求解出方程 $ax + by = \gcd(a, b)$ 的一组解，将 $x, y$ 分别乘上 $\frac c {\gcd(a, b)}$ 即可得到 $ax + by = c(\gcd(a, b)\mid c)$ 的一组解。

实战

Vijos 1279

题目

数学题，可证明答案为 $a + b - \gcd(a, b)$，也可根据这经典的图求解。

long long gcd(int a, int b) {
    if(b == 0) return 0;
    return a / b * b + gcd(b, a % b);
}