记录：扩展欧几里得算法

本文遵循 CC BY-NC-ND 4.0 协议，作者：$\text{U•ェ•*U}$，转载请获得作者授权。

前置知识

裴蜀定理/贝祖定理：若 $a,b$ 是整数，且 $\gcd (a,b)=d$，那么对于任意整数 $x,y$，$a\times x+b\times y=k$ 中的 $k$ 一定是 $d$ 的倍数。（特别地，如果 $a,b$ 是整数，那么一定存在整数 $x,y$ 使得$a\times x+b\times y=\gcd (a,b)$）

引入

引入扩展欧几里得算法，可用于求解以下几种问题：

• 给定两个非零的整数 $a$ 和 $b$，求一组整数解 $(x,y)$ 使得 $a\times x+b\times y=\gcd (a,b)$ 成立，其中 $\gcd (a,b)$ 表示 $a$ 和 $b$ 的最大公约数。
• 逆元

从欧几里得算法推导：
$$\begin{gathered} \gcd (x,y)\to \gcd (y,x\mathrm{mod}y) \\ \Downarrow \\ \forall x_n=1,y_n=0 \\ \forall a\times x_1+b\times x_1=\gcd \\ \Downarrow \\ \forall b\times x_2+(a\mathrm{mod}b)\times y_2=\gcd \\ \forall a\times x_1+b\times x_1=b\times x_2+(a\mathrm{mod}b)\times y_2 \\ \forall a\times x_1+b\times y_1=a\times y_1+b\times (x_2\times \frac{a}{b}\times y_2) \end{gathered}$$

于是反推出原来的值（$x_1,y_1$）：

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

证明：
[TODO]

求同余式

对两个整数 $a,b$，如果它们除以 $d$ 的余数相同，则称它们模 $d$ 同余，记作 $a\equiv b(\mathrm{mod}d)$。

在同余号两侧同时加、减、乘任意整数，同余式仍成立。

我们设一个同余式 $ax\equiv c(\mathrm{mod}m)$，那么可以分讨求解：

• 若 $c\mathrm{mod}\gcd (a,m)\ne 0$，则同余方程 $ax\equiv c(\mathrm{mod}m)$ 无解。
• 若 $c\mathrm{mod}\gcd (a,m)=0$，则同余方程的解为 $x’ = x + \frac{\gcd(a, m)}{m}\times \mathbb{N} $。

求逆元

对任意给定的 $x$ 和 $p$，显然 $x\times x^{-1}\equiv 1(\mathrm{mod}p)$。可以利用
这个式子计算 $x^{-1}$。

其中 $x$ 和 $p$ 是已知量，所以上式是一个不定方程，$x^{-1}$ 和 $k$
是变量。用 $\text{exgcd}$ 求解可以得到 $x^{-1}$。

$\text{C++}$ 代码（线性求逆元）：

int n, p, inv[3000010];
signed main() {cin >> n >> p;inv[1] = 1;cout << 1 << endl;for (int i = 2; i <= n; i ++) {inv[i] = (int)(p - p / i) * inv[p % i] % p;printf("%lld\n", inv[i]);}return 0;
}