扩展欧几里得算法

裴蜀定理

形式

若 $a,b\in\mathbb{Z}$，那么对于 $\forall x,y\in\mathbb{Z}$，$\gcd(a,b)\mid a\times x+b\times y$。

此外，一定 $\exist\,x,y \in \mathbb{Z}$，使得 $a\times x+b\times y=\gcd(a,b)$ 成立。

证明

证明第一点：
$$ \begin{array}{l} \because \gcd(a,b)\mid a,\gcd(a,b)\mid b\\ \therefore \gcd(a,b)\mid ax,\gcd(a,b)\mid by\,\,(x,y\in\mathbb{Z})\\ \therefore \gcd(a,b)=a\times x+b\times y \end{array} $$

证明第二点：
设 $a\times x+b\times y$ 的最小正整数值为 $r$，考虑证明 $a\bmod r=0$。

设 $p=\Big\lfloor\dfrac{a}{r}\Big\rfloor$，则可得 $a\bmod r=a-p\times r$。

代入 $r$，得到 $a\bmod r=a-p\times(a\times x+b\times y)$。

进一步可得 $a\times(1-p\times x)+b\times (-p\times y)$，这就是 $ax'+by'$ 的形式。

因为 $0\le a\bmod r
所以 $a\bmod r = 0$，即 $r$ 是 $a$ 的因数。

同理可得 $r$ 也是 $b$ 的因数。

所以 $r$ 是 $a,b$ 的公因数，即 $r\mid\gcd(a,b)$。

又因为 $a\times x+b\times y$ 都是 $\gcd(a,b)$ 的倍数，所以 $\gcd(a,b)\mid r$。

故 $r=\gcd(a,b)$。

$\textbf{Exgcd}$

首先考虑欧几里得算法是如何求解 $\gcd(a,b)$ 的。

当 $b=0$ 时，$a$ 即为 $a,b$ 的最大公约数。
求出 $\gcd(b,a\bmod b)$，设为 $g_0$。
令 $g=g_0$，$g$ 就是 $a,b$ 的最大公约数。

令 $d=\gcd(a,b)$ 于是可以仿照这个过程，求解不定方程：

当 $b=0$ 时，$ax+by=d$ 的解是 $x=\dfrac{d}{a}$，$y$ 任意。
求出 $bx+(a\bmod b)y=d$ 的一组解，设为 $(x_0,y_0)$。
令 $(x,y)=f\big((x_0,y_0)\big)$，那么 $(x,y)$ 就是 $ax+by=d$ 的一组解。

其中 $f\big((x_0,y_0)\big)$ 表示对 $(x_0,y_0)$ 的一种变换。

现在的问题就是，如何通过 $(x_0,y_0)$ 得到 $(x,y)$。

PS在欧几里得算法中，$\gcd(a,b)=\gcd(b,a\bmod b)$，故下面的式子中 $d$ 是相等的。

已知 $bx_0+(a\bmod b)y_0=d$，转化形式可得：
$$ bx_0+(a-\Big\lfloor\dfrac{a}{b}\Big\rfloor b)y_0=d $$
将 $a,b$ 提出来，可得
$$ ay_0+b(x_0-\Big\lfloor\dfrac{a}{b}\Big\rfloor y_0)=d=ax+by $$
通过待定系数法，可得
$$ \begin{cases} x=y_0\\ y=x_0-\Big\lfloor\dfrac{a}{b}\Big\rfloor y_0\\ \end{cases} $$

具体实现中，在数学上，当最后 $b=0$ 时 $y$ 可以取任意值，但是如果 $y$ 取得很大的话，中途中可能会超过 int 和 long long 的存储范围。

但是如果最后 $b=0$ 时 $y=0$，那么对于其它的迭代步骤，求解 $ax+by=\gcd(a,b)$ 得到的一组解 $(x,y)$ 一定满足：
$$ \begin{cases} |x|\le\Bigg|\dfrac{b}{2\times \gcd(a,b)}\Bigg|\\ \hspace{0.5 mm}|y|\le\Bigg|\dfrac{a}{2\times \gcd(a,b)}\Bigg|\\ \end{cases} $$

证明：

PS：这里只考虑 $a>b$ 的情况，显然 $a\le b$ 在依次迭代后会变成 $a>b$ 的情况。

首先，当 $a\bmod b=0$ 时，因为 $a>b$ 且 $a$ 是 $b$ 的倍数，所以 $a\ge 2\times b$。迭代得到的解
$$ \begin{cases} x=y_0=0<\Bigg|\dfrac{b}{2\times \gcd(a,b)}\Bigg|\\ y=x_0-\Big\lfloor\dfrac{a}{b}\Big\rfloor y_0=x_0=\Bigg|\dfrac{2\times b}{2\times b}\Bigg|\le\Bigg|\dfrac{a}{2\times \gcd(a,b)}\Bigg| \end{cases} $$
其次，设 $bx+(a\bmod b)y=\gcd(b,a\bmod b)$ 得到的解为 $(x_0,y_0)$，满足：
$$ \begin{cases} x_0\le\Bigg|\dfrac{a\bmod b}{2\times \gcd(b,a\bmod b)}\Bigg|\\ \hspace{0.5 mm}y_0\le\Bigg|\dfrac{b}{2\times \gcd(b,a\bmod b)}\Bigg| \end{cases} $$
则 $ax+by=\gcd(a,b)$ 得到的解 $(x,y)$ 也满足：

$|x|=|y_0|\le\Bigg|\dfrac{b}{2\times \gcd(b,a\bmod b)}\Bigg|=\Bigg|\dfrac{b}{2\times\gcd(a,b)}\Bigg|$；

由于 $|x_0|\le\Bigg|\dfrac{a\bmod b}{2\times \gcd(b,a\bmod b)}\Bigg|$，$\Bigg|\Big\lfloor\dfrac{a}{b}\Big\rfloor y_0\Bigg|\le \Bigg|\dfrac{\big\lfloor\frac{a}{b}\big\rfloor}{2\times\gcd(a,b)}\Bigg|$，

所以

$$ |y|=\Bigg|x_0-\Big\lfloor\dfrac{a}{b}\Big\rfloor y_0\Bigg|\le|x_0|+\Bigg|\Big\lfloor\dfrac{a}{b}\Big\rfloor y_0\Bigg|=\Bigg|\dfrac{\big\lfloor\frac{a}{b}\big\rfloor b+a\bmod b}{2\times \gcd(a,b)}\Bigg|=\Bigg|\dfrac{a}{2\times \gcd(a,b)}\Bigg| $$

又可以发现，设 $ax+by=d=k\times\gcd(a,b)$，那么每次得到的解都是在求解 $ax+by=\gcd(a,b)$ 时的解的 $k$ 倍，所以不管 $d$ 取多少，在最后的迭代中取 $x=k,y=0$ 同样是没有问题的。

求出一对解 $x_{0},y_{0}$ 后，可求出通解为：
$$ \begin{cases} x=x_{0}+\dfrac{b}{\gcd(a,b)}\times t\\ y=y_{0}-\dfrac{a}{\gcd(a,b)}\times t \end{cases} \qquad t\in\mathbb{Z} $$

时间复杂度与欧几里得算法相同，故时间复杂度为 $O(\log\max\{a,b\})$。

$\textbf{Code}$

using lint = long long;

lint exgcd(lint a, lint b, lint &x, lint &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  lint d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}