浅谈拓展欧几里得算法（Exgcd）

· · 算法·理论

本文章的前置知识点：辗转相除法求最小公约数。

常常遇到 ax \equiv b \pmod P 却不知道怎么做？看到 ax+by=m 不会解？你可能需要 Exgcd（拓展欧几里得算法）。

Exgcd 可以做什么？

Exgcd 最基础的用法是用来求 ax+by=\gcd(a,b) 的整数解，由而也可以用来解二元一次不定方程，对有理数取余，求逆元等等。Exgcd 还是 ExCRT 的基础，并运用于许多组合计数问题中。

Exgcd 的原理和实现

如何求一个 ax+by=\gcd(a,b)(a,b \in \mathbb{N^+}) 的方程？

Exgcd 的思想与辗转相除法是相似的，已知 \gcd(a,b)=\gcd(b,a \bmod b)，因此我们可以先解以下方程： bx+(a\bmod b)y=\gcd(b,a \bmod b)。

我们最终会得到 b=0 的特殊情况，从辗转相除法来看，此时的 a 就等于 \gcd(a,b)。代入 x=1,y=0 即可。

现在我们要解决的是如何通过方程 bx+(a\bmod b)y=\gcd(b,a \bmod b) 的解推出方程 ax+by=\gcd(a,b) 的解。

对以上式子变形可以得到 $ay+b(x-y \cdot \lfloor\frac{a}{b}\rfloor)=\gcd(a,b)$。我们发现，这个形式不是和 $ax+by=\gcd(a,b)$ 一样吗？因此我们得到了推出 $ax+by=\gcd(a,b)$ 的公式： 设 $bx+(a\bmod b)y=\gcd(b,a \bmod b)$ 的解为 $x=x',y=y'$，则 $ax+by=\gcd(a,b)$ 的解为： $$\left\{ \begin{aligned} x & =y' \\ y & =x'-y' \cdot \lfloor\frac{a}{b}\rfloor \\ \end{aligned} \right.$$ 我们一层层递归回去就可以推出原方程的解了。 ```cpp ll a,b,g,x,y,tmp; void exgcd(ll a,ll b){ if(b==0){ g=a; x=1; return; }else{ exgcd(b,a%b); tmp=x; x=y; y=tmp-y*(a/b); } } ``` ## 裴蜀定理 许多 Exgcd 的应用都需要裴蜀定理。 裴蜀定理，即存在 $x,y \in \mathbb{Z}$ 使 $ax+by=m(a,b,m \in \mathbb{Z})$ 的充要条件是 $m$ 是 $\gcd(a,b)$ 的倍数。 充分性证明：设 $k=\frac{m}{\gcd(a,b)}$，根据已知条件，$k \in \mathbb{Z}$。根据 Exgcd 我们可以找到一组 $x',y'$ 使得 $ax'+by'=\gcd(a,b)$ 成立。方程两边各自乘上 $k$ 得 $akx'+bky'=m$ 成立，因此存在 $x=kx',y=ky'$ 使条件成立。 必要性证明：假设 $\frac{m}{\gcd(a,b)} \notin \mathbb{Z}$，我们可以将方程 $ax+by=m$ 变换为 $\frac{ax}{\gcd(a,b)}+\frac{by}{\gcd(a,b)}=\frac{m}{\gcd(a,b)}$，根据 $\gcd(a,b)$ 的定义，若 $x,y \in \mathbb{Z}$，那么 $\frac{ax}{\gcd(a,b)},\frac{by}{\gcd(a,b)} \in \mathbb{Z}$，$\frac{m}{\gcd(a,b)} \notin \mathbb{Z}$，这是矛盾的。因此存在整数解时，$m$ 一定是 $\gcd(a,b)$ 的倍数。 ## 例题：P1082 同余方程 ### 题目描述 求关于 $ x$ 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解，保证 $2 \leq a,b \leq 2,000,000,000$，方程有解。 ### 如何使用 Exgcd 解决此题？ 我们注意到这个方程可以变换为：$ax+by=1$，即求 $x$ 最小的整数解。保证该方程有解，因此该方程右侧的常数一定是 $\gcd(a,b)$ 的倍数，而该常数是 $1$。显然 $\gcd(a,b)$ 就是 $1$，直接 Exgcd 就能得出一组解。 我们要求的是最小整数解。我们可以发现若 $ax+by=1$ 成立，那么 $a(x-\frac{b}{\gcd(a,b)})+b(y+\frac{a}{\gcd(a,b)})=1$ 必然成立，同时不存在更小的整数使得这个推论成立，因为 $\frac{ab}{\gcd(a,b)}$ 即为 $a,b$ 的最小公倍数，不存在更小的数字同时为 $a,b$ 的倍数。 因此设 $x$ 的特定解为 $x'$，则 $x$ 的最小非负整数解即为 $x \bmod \frac{b}{\gcd(a,b)}$。显然不会出现 $0$，不需要特判。不过在具体实现上可能出现 $x'<0$ 的情况，需要先模，转换成正整数再模一次。 ## 例题：P5656 【模板】二元一次不定方程 (exgcd) ### 题目描述 给定不定方程 $$ax+by=c$$ 若该方程无整数解，输出 $-1$。 若该方程有整数解，且有正整数解，则输出其**正整数**解的数量，所有**正整数**解中 $x$ 的最小值，所有**正整数**解中 $y$ 的最小值，所有**正整数**解中 $x$ 的最大值，以及所有**正整数**解中 $y$ 的最大值。 若方程有整数解，但没有正整数解，你需要输出所有**整数解**中 $x$ 的最小正整数值， $y$ 的最小正整数值。 正整数解即为 $x, y$ 均为正整数的解，$\boldsymbol{0}$ **不是正整数**。 整数解即为 $x,y$ 均为整数的解。 $x$ 的最小正整数值即所有 $x$ 为正整数的整数解中 $x$ 的最小值，$y$ 同理。 **【数据范围】** 对于 $100\%$ 的数据，$1 \le T \le 2 \times {10}^5$，$1 \le a, b, c \le {10}^9$。 ### 如何使用 Exgcd 解决此题？ 首先我们需要判断出有没有解，根据前文所述的裴蜀定理：存在 $x,y \in \mathbb{Z}$ 使 $ax+by=m(a,b,m \in \mathbb{Z})$ 的充要条件是 $m$ 是 $\gcd(a,b)$ 的倍数，我们就可以直接的下定判断——若 $m$ 是 $\gcd(a,b)$ 的倍数则有解，否则无解。 同样地，根据 Exgcd，我们可以求出 $ax+by=\gcd(a,b)$ 的一组解，然后将 $x,y$ 一起乘上 $\frac{c}{\gcd(a,b)}$ 就可以得到一组特定解。利用若 $ax+by=c$ 成立，那么 $a(x-\frac{b}{\gcd(a,b)})+b(y+\frac{a}{\gcd(a,b)})=c$ 成立的式子，可以推出具体解的情况。 具体地，若 $x,y \in \mathbb{N^+}$ 成立，当 $x$ 取到最小正整数解时 $y$ 是最大的，此时要是 $y$ 还是没有取到正整数的话，那就没有正整数解了，否则是有的。具体的做法可以参考前文的同余方程，不过此处需要特判可能的 $0$。 ## 例题：P2613 【模板】有理数取余 ### 题目描述 给出一个有理数 $c=\frac{a}{b}$，求 $c \bmod 19260817$ 的值。 这个值被定义为 $bx\equiv a\pmod{19260817}$ 的解。 对于所有数据，保证 $0\leq a \leq 10^{10001}$，$1 \leq b \leq 10^{10001}$，且 $a, b$ 不同时是 $19260817$ 的倍数。 ### 如何使用 Exgcd 解决此题？ 有理数 $\frac{a}{b}$ 对 $P$ 取模定义为 $bx\equiv a\pmod{P}$ 的解，此处即为求解 $b$ 的逆元（同余方程 $bx\equiv 1\pmod{P}$ 的解），用 Exgcd 求解即可（对于任意模数都可以使用这种方法）。此题需要边输入边取模。 ## 例题：P1516 青蛙的约会 ### 题目描述 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经 $0$ 度处为原点，由东往西为正方向，单位长度 $1$ 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 $x$，青蛙 B 的出发点坐标是 $y$。青蛙 A 一次能跳 $m$ 米，青蛙 B 一次能跳 $n$ 米，两只青蛙跳一次所花费的时间相同。纬度线总长 $L$ 米。现在要你求出它们跳了几次以后才会碰面。 对于 $100\%$ 的数据，$1 \le x \ne y \le 2 \times 10^{9}$，$1 \le m, n \le 2 \times 10^{9}$，$1 \le L \le 2.1 \times 10^{9}$。 形式化题面：判断是否存在一个最小的 $k$，使 $x+km \equiv y+kn \pmod L$，并求这个最小的 $k$。 ### 如何用 Exgcd 求解此题？ 不妨设 $m>n$。 根据同余的性质，有 $k(m-n) \equiv y-x \pmod L$，并且可以得出一个方程：$k(m-n)+aL=y-x$。使用 Exgcd 可以求解该方程的最小正整数解或判断其无解。 当 $m<n$ 时，交换两只青蛙的信息即可。 ## 结语 恭喜你，学会了 Exgcd 的初步使用！！！ 有没有人和你说过，你学数论的样子真的很帅。 如果没有? 那么，就在上一秒，我对你说了。