【模板】扩展欧几里得算法

用于解形如 $ax+by=\gcd(a,b)$ 的不定方程。

void exgcd(int a, int b, int &g, int &x, int &y) {
    if (!b) x = 1, y = 0, g = a;
    else {
        exgcd(b, a % b, g, x, y);
        int t = x;
        x = y;
        y = t - a / b * y;
    }
}

如何理解

虽然不知道在推什么但是确实推出来了（？

$\begin{aligned}
\because ax+by&=\gcd(a,b)\
\gcd(a,b)&=\gcd(b,a \bmod b)\
\therefore ax+by&=bx+(a \bmod b)y\
&=bx+(a-\left\lfloor\dfrac{a}{b}\right\rfloor b)y\
\therefore ax+by&=ay+b(x-\left\lfloor\dfrac{a}{b}\right\rfloor y)
\end{aligned}$

代码的第4~7行就是从从最后得到的 $ax+by=ay+b(x-\left\lfloor\dfrac{a}{b}\right\rfloor y)$ 得到的。

进一步

已知 $ax+by=\gcd(a,b)$ ，有 $\dfrac{a}{\gcd(a,b)}x+\dfrac{b}{\gcd(a,b)}y=1$

所以对于 $ax+by=z$ 就有 $\dfrac{az}{\gcd(a,b)}x+\dfrac{bz}{\gcd(a,b)}y=z$

所以该方程有解的充要条件是 $\gcd(a,b) \mid z$

再进一步

我们已经得到了一组 $ax+by=\gcd(a,b)$ 的解，求该方程的所有整数解。

设得到的一组解为 $x_0,y_0$ ，设另一组解为 $x_1,y_1$。

显然有 $ax_0+by_0=ax_1+by_1=\gcd(a,b)$ 。

移项可得 $a(x_0-x_1)=b(y_1-y_0)$。

设 $\gcd(a,b)=g$，则有 $\dfrac{a}{g}(x_0-x_1)=\dfrac{b}{g}(y_1-y_0)$。

由于 $\dfrac{a}{g}$ 与 $\dfrac{b}{g}$ 互质，则 $(x_0-x_1)=k\frac{b}{g}, (y_1-y_0)=k\frac{a}{g}$

所以另一组解为

$\begin{aligned}
x_1&=x_0-k\dfrac{b}{g}\\
y_1&=y_0+k\dfrac{a}{g}\\
(k&\in\mathbb{Z})
\end{aligned} $