辗转相除法

辗转相除法，又称为 Euclid 算法（Euclid's algorithm），可以求得两个数的最大公因数。

过程

辗转相除法利用这两个基本性质：

• (a, b) = (b, a \bmod b)
• (a, 0) = a

设 a, b 是两个正整数，则辗转相除法的过程如下：

由于该序列中恒有 b > r_1 > r_2 > \cdots，余数一定在有限步内可以达到 0，且由于对任意整数 x, y 有 (x, y) = (y, x \bmod y)，故 (a, b) = (b, r_1) = (r_1, r_2) = \cdots = (r_{n - 1}, r_n) = (r_n, 0) = r_n，即倒数第二步所得的 r_n 即为 a, b 的最大公因数。

代码

利用递归和三目运算符，函数体一行即可实现：

int gcd(int a, int b)
{ return b == 0? a: gcd(b, a % b);}

以上算法对 a, b 为 0 的情况也成立。

但是当 a, b 存在负数时，由于 C++ 取模运算的实现，返回值可能是负数，但依然是两者的负的最大公因数。

时间复杂度

两个数

在辗转相除法 r_3 = r_1 \bmod r_2, r_4 = r_2 \bmod r_3 的过程中，若 r_3 \le r_2 / 2，则 r_4 < r_2 / 2 < r_1；若 r_2 / 2 < r_3 < r_2，则 r_2 = 1 \cdot r_3 + r_4，故 r_4 = r_2 - r_3 < r_2 / 2。

因此，经过两次递归，函数的第二元将缩小至不足原来的一半，因此调用 gcd(a, b) 时，时间复杂度上界是 O(\log(\min(a, b)))。

实际运行中，在随机数上大多数达不到该复杂度上界。达到上界的一种情况是 Fibonacci 数列。

多个数

使用 Euclid 算法，求 n 个数的 GCD 时，其最坏复杂度并不会达到 O(n \log V)。由于每次求 GCD 时，时间复杂度都取决于较小的一个数，且每次 GCD 的减少都会至少折半，因此减少的次数不会超过 O(\log V)（V = \min(a_1, \dots, a_n)）。

再考虑读取 n 个数，以及可能存在的常数次交换和判断，时间复杂度为 O(n + \log V)。

扩展 Euclid 算法

由 Bezout 等式，若 d = (a, b)，则存在整数 u, v 使得 au + bv = d。扩展 Euclid 算法可以求出一对满足该条件的整数。

过程

依然使用递归，递归的正确性可以用数学归纳法证明。

在 a, b 辗转相除的过程中，对第二元 b 归纳，若 b = 0，则显然 d = a，故 u = 1, v = 0 是满足 au + bv = d 的一对整数。

设 b > 0，假设第二元小于 b 时的系数已经求得，设 a = qb + r，0 \le r < b，则 d = (a, b) = (b, r)，由归纳假设，可求得 u', v' 使得 bu' + rv' = d，则 au + bv = b u' + rv' = b u' + (a - qb) v' = a v' + b (u' - q v')，对比系数得到 u = v', v = u' - q v'。

代码

pair<int, int> exgcd(unsigned a, unsigned b) {
    if (b == 0) { return {1, 0};}
    tie(u, v) = exgcd(b, a % b);
    return {v, u - (a / b) * v};}

应用

线性同余方程

设 (a, m) = 1，则线性同余方程

有唯一解。该方程也可视为二元一次不定方程

先用扩展 Euclid 算法求得 ax' + my' = 1 的一组解 x', y'，然后令 x = bx', y = by'，容易验证 ax+my = b(ax' + my') = 1，所以 x = bx', y = by' 即为一组解。