扩展欧几里得算法求$a$对模$b$的逆
当$(a, b)=1$时,有
$$\exists x, y \in Z, \; ax+by=1$$
扩展欧几里得算法证明如下:
设$a \gt b$。
当$b=0$时,有
$$a \times 1+b \times 0=a=(a, b)=1$$
此时$x=1, \; y=0$。
当$b \neq 0$时,有
$$
\left\{
\begin{align}
a \times x_1+b \times y_1&=1 \\
b \times x_2+a \bmod b \times y_2&=1
\end{align}
\right.
$$
所以
$$a \times x_1+b \times y_1=b \times x_2+a \bmod b \times y_2$$
将$a \bmod b=a-a/b \times b$代入,得
$$a \times x_1+b \times y_1=b \times x_2+a \times y_2-a/b \times b \times y_2$$
那么$x_1=y_2, \; y_1=x_2-a/b \times y_2$。
由此得证。
void extend_gcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return; } int ret = extend_gcd(b, a % b, y, x); y -= a / b * x; }
费马小定理求$a$对模$p$的逆
当$p$是质数且$p \nmid x$时,有
$$x^{-1} \equiv x^{p-2} \pmod p$$
证明如下:
根据费马小定理,当$p$是质数时,有
$$\forall x \in Z, \; x^p \equiv x \pmod p$$
当$p \nmid x$时,有
$$
\begin{align}
x^{p-1} &\equiv 1 \pmod p \\
x^{-1} &\equiv x^{p-2} \pmod p
\end{align}
$$
由此得证。
$O(n)$时间求出$1..n$对模$p$的逆
当$p$是质数且$1 \lt i \lt p$时,有
$$i^{-1} \equiv (p-p/i) \times (p \bmod i)^{-1} \pmod p$$
证明如下:
令$t=p/i, \; k=p \bmod i$。易知
$$
\begin{align}
t \times i+k &\equiv 0 \pmod p \\
k &\equiv -t \times i \pmod p
\end{align}
$$
等式两边同时除以$ik$,得
$$
\begin{align}
i^{-1} &\equiv -t \times k^{-1} \pmod p \\
i^{-1} &\equiv -p/i \times (p \bmod i)^{-1} \pmod p
\end{align}
$$
即
$$i^{-1} \equiv (p-p/i) \times (p \bmod i)^{-1} \pmod p$$
由此得证。
void get_inv() { inv[1] = 1; for (int i = 2; i < MOD; ++i) { inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD; } }
求$b \mid a$时${a \over b}$在模$n$意义下的值
当$b \mid a$时,有
$${a \over b} \bmod n=a \bmod (bn) / b$$
证明如下:
设
$${a \over b} \bmod n = x$$
则有
$$
\begin{align}
{a \over b}&=kn+x \\
a&=kbn+bx
\end{align}
$$
因为$0 \le x \lt n$,所以
$$
\begin{align}
a \bmod (bn)&=bx \\
x&=a \bmod (bn) / b
\end{align}
$$
由此得证。