题解：P5656 【模板】二元一次不定方程 (exgcd)

DengStar · 2025-05-20 17:46:23 · 题解

扩展欧几里得算法

前置知识：欧几里得算法

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD）用于求形如

的二元一次不定方程的所有整数解。

（为了方便，我们认为 a, b, c \ge 0。对于负数的情况可能需要多一点讨论。）

有解性判定——裴蜀定理

裴蜀定理（Bézout's lemma）给出了二元一次不定方程有整数解的充要条件：方程 ax + by = c 有解当且仅当

证明

设 \gcd(a, b) = g。

必要性 由于等式左边一定是 g 的倍数，因此等式右边也必须是 g 的倍数。

充分性 为了方便，不妨设 c = g。如果在这种情况下存在某组解，那么当 c 是 g 的倍数时，把这组解扩大若干整数倍，就可以得到原方程的解。所以研究有解性时只需考虑这种情况。

设 S = \{xa + yb | x, y \in \mathbb{Z}\}。下面证明 S 中的最小正元素为 g。

首先，S 中至少有一个正元素（a 和 b，说“一个”是因为二者可能相同），设最小的正元素为 d_0 = x_0a + y_0b。另取 S 中任一正元素 p = x_1a + y_1b，考虑它对 d 的带余除法 p = qd_0 + r，那么

因此 r \in S。由于 r 是 p 除以 d_0 的余数，所以 0 \le r < d_0。如果 r 为正数，就与 d_0 的最小性矛盾。因此 r = 0。那么可以推出：S 中任意正元素都是 d_0 的倍数。特别地，有 d_0 \mid a 和 d_0 \mid b，因此 d_0 是 a 和 b 的公约数。

另一方面，由于 a 和 b 都是 g 的倍数，而 d_0 是 a 和 b 的线性组合，因此 d_0 也是 g 的倍数（在 I 章中我们已经用过了这个结论）。结合两点可知 d_0 = g。至此，我们就证明了当 c = g 时 ax + by = c 一定有解。对于更一般的情况，如果 c = c'g，把 ax + by = g 的每个解乘 c' 倍就得到了 ax + by = c 的解，所以两个方程的有解性相同。\Box

解的形式及个数

我们可以进一步说明，只要有解，就有无数组解。设 (x_0, y_0) 是任意一组解，a = a'g，b = b'g，则方程的解集为

换句话说，把 x 加上若干个 b'，同时把 y 减去若干个 a' 不改变 ax + by 的值，因为 a \cdot \dfrac{kb}{g} = b \cdot \dfrac{ka}{g}。另外，这两者显然都是整数，所以变换后得到的还是整数解。

另一方面，对于任意的解 (x', y') 满足 ax' + by' = c，把此等式与 ax_0 + by_0 = c 相减，有

由于 a = a'g，b = b'g，所以

左边是 a' 的倍数，因此右边也是 a' 的倍数。又因为 a' 与 b' 互质，所以 y' - y_0 是 a' 的倍数。设 y' - y_0 = a'k，则 y' = y_0 + a'k，代入得 x' = x_0 - b'k，这就把 (x', y') 转化成了 A 中的形式。所以，A 确实包含了方程的所有整数解。

过程

现在我们要求出 ax + by = c 的任意一组解。先根据裴蜀定理判断是否有解，如果有解，为了方便仍然假设 c = g。求出一组解以后我们可以根据通解的公式求出其它的解。

我们使用和欧几里得算法类似的迭代方法：每次迭代都会使 a 和 b 减小，最终 b 减小到 0 时就可以得到显然的解，然后反推原方程的解。

具体地，如果 b = 0，那么 \gcd(a, b) = a，方程可以写为 ax + 0y = a。此时显然 x = 1, y = 0 是一组解。当然，y 可以取任何整数，但取 0 比较方便，并且这保证了最终得到的原方程的解不会太大，

否则，我们把原方程迭代为一个新的方程：a'x + b'y = \gcd(a', b')，其中 a' = b，b' = a \bmod b。这样做的意义和欧几里得算法是相同的：迭代后方程的系数会减小，最终到达边界情况时就能得到解。那么，假设我们求出了这个方程的一组解 (x_1, y_1)，要如何反推回原方程的一组解 (x_0, y_0) 呢？

由于 \gcd(a, b) = \gcd(b, a \bmod b)，所以 \gcd(a, b) = \gcd(a', b')，因此

把 a \bmod b 改写为 a - b \cdot \left\lfloor \dfrac{a}{b} \right\rfloor，那么

整理等式右边，得到

对比两边得到

这就得到了两个方程解的关系。

此算法时间复杂度的分析和欧几里得算法完全相同，二者的时间复杂度都是 O(\log w)，其中 w 是 a 和 b 的值域，这里不再赘述。

以下是一份 exgcd 的示例代码，它返回一个二元组（pair），表示方程的解 x, y：

auto exgcd(int a, int b) {
    if(b == 0) {
        return make_pair(1, 0);
    }
    auto [x, y] = exgcd(b, a % b);
    return make_pair(y, x - (a / b) * y);
}

这种写法比较美观，因为函数的返回值恰好就是方程的解。但我不知道使用 pair 会不会导致常数偏大。大多数人使用的是一种传引用的写法：

void exgcd(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1, y = 0;
        return;
    }
    int x0, y0;
    exgcd(b, a % b, x0, y0);
    x = y0, y = x0 - (a / b) * y0;
}

值域分析