exgcd（扩展欧几里得）学习笔记

前置芝士

• 基础的模、整数运算；
• $\gcd$ 的求法，即 $\gcd(a, b) = \gcd(b,a \bmod b)$；
• 裴蜀定理，二元一次方程方程 $ax+by=c$ 有解的充要条件是 $\gcd(a, b) \mid c$；

正文部分

$\tt{exgcd}​$ 用于求出二元一次方程 $ax+by=c​$ 的一组特解。

首先根据裴蜀定理，可以先判掉无解的情况。这样我们可以先计算 $ax+by=\gcd(a,b)$ 这个方程的解，再乘上 $\dfrac{c}{\gcd(a,b)}$。

既然是 $\tt{exgcd}$，那我们考虑 $\gcd$ 是怎么做的，即缩小问题规模，把 $\gcd(a,b)$ 转化为 $\gcd(b, a \bmod b)$ 递归求解。

同样的思路，我们把方程转化为 $bx+(a\bmod b)y=\gcd(b,a \bmod b)$ 递归求解。所以现在的问题是，我们知道一个方程：

$$bx + (a \bmod b)y = \gcd(b, a \bmod b)$$

的一组解 ${ x_2, y_2}$，求

$$ax+by=\gcd(a,b)$$

的一组解 ${ x_1, y_1}$。因为

$$\gcd(a,b)=\gcd(b,a \bmod b)$$

，所以

$$bx_2+(a \bmod b)y_2=\gcd(a,b)$$

然后用拆开取模的小技巧可以得到：

$$bx_2+ \left (a-b \left \lfloor \dfrac{a}{b} \right \rfloor \right )y_2 = \gcd(a,b)$$

继续化简：

$$bx_2+ay_2 - b \left (\left \lfloor \dfrac{a}{b} \right \rfloor y_2 \right ) = \gcd(a,b)$$ $$\Rightarrow ay_2 + b \left (x_2 - \left \lfloor \dfrac{a}{b} \right \rfloor y_2 \right) = \gcd(a,b)$$

最后得到：

$$\begin{cases} \begin{align} &x_1 = y_2\\ &y_1 = \left (x_2 - \left \lfloor \dfrac{a}{b} \right \rfloor \right ) \end{align} \end{cases}$$

考虑边界，当 $b = 0$ 时，$x = 1$，$y = 0$，时间复杂度与 $\gcd$ 相同， $\Theta(\log \ n)​$。

CODE

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

参考：OI Wiki。