三分钟学会扩展欧几里得算法
高一学会打扩展欧几里得的代码，然后抄代码抄了三年。
我嘲笑那些嘲笑我连 exgcd 都不会的人，会这个东西有用吗？反正都是背代码。直到这道题在高代的作业里面出现。
辛苦男朋友了。
欧几里得算法
在一个唯一分解环 (UFD) 内，有以下性质：
$$(a, b) = (b, a \bmod{b}) $$
因此可以使用辗转相除法来求两个数的最大公约数。
扩展欧几里得算法
为解决如下问题：
$$ ax + by = (a, b)$$
已知 $a$, $b$，求满足上式的 $x, y$ 。
我们考虑，如果有：
$$ bx_0 + (a \bmod b)y_0 = (b, a \bmod b) $$
即有：
$$ ay_0 + b(x_0 - \lfloor \frac{a}{b} \rfloor y_0 ) = (a, b) $$
于是可以在欧几里得算法递归到底端回传的时候每次更新 $x, y$ 。
计算全部解
上式只是给出了一个合法解。如何求出全部满足条件的 $x, y$ ？
设当前唯一分解环为 $R$，我们声明所有解都有如下形式：
$$ a(x_0 + \frac{b}{(a, b}k) + b(y_0 - \frac{a}{(a, b)}k) = (a, b), k \in R$$
首先，每个满足上述形式的 $x, y$ 都显然合法，我们只需考虑证明不存在其他的解。
若存在 $x_0, x_1, y_0, y_1$ 均为合法解，那么有： $$ a(x_0 - x_1) + b(y_0 - y_1) = 0 $$
也就是，
$$ \frac{a}{(a, b)}(x_0 - x_1) = \frac{b}{(a, b)}(y_0 - y_1)$$
由最大公约数的定义，知 $\frac{a}{(a, b)}$ 与 $\frac{b}{(a, b)}$ 互素。由唯一分解性质可知，$\frac{a}{(a, b)}$ 是 $(y_0 - y_1)$ 的倍数，另一边同理。
于是声明成立。