数论：逆元

什么是逆元？

若 $ax \equiv 1 \pmod b$，则称 $x$ 是 $a$ 关于模 $b$ 的逆元，常记做 $a^{-1}$。

上式等价于 $ax + by = 1$，因此，一种求逆元的方法就是利用扩欧解方程 $ax + by = 1$。

显然，逆元不一定存在：其存在的充要条件为 $(a, b) = 1$。

推论：$p$ 是质数，$p$ 不整除 $a$，则 $a$ 模 $p$ 的逆元存在。

结论：在 $[0, b)$ 的范围内，$a$ 关于模 $b$ 的逆元（若存在）是唯一的。

证明：
反证法，若 $a$ 有两个逆元 $0 < x_1 < x_2 < b$，
即 $ax_1 ≡ ax_2 ≡ 1 \pmod b$，
那么有 $b|a(x_2 - x_1)$ 成立。
又由于 $(a, b) = 1$，因此 $b|(x_2 - x_1)$。
其中 $0 < x_2 - x_1 < b$，产生了矛盾。

求解逆元

$$
ax\equiv 1 \pmod p
$$

扩欧

上面已经提到过了，直接解方程 $ax + py = 1$ 即可。这个方法十分容易理解，而且对于单个查找效率不错，尤其是在模数比较大的时候。

这个做法在 $a,p$ 互质，但 $p$ 不是质数时也可以使用。其他方法均要求 $p$ 必须为素数。

快速幂

这个做法要利用费马小定理：若 $p$ 为素数，$a$ 为正整数，且 $a,p$ 互质，则有
$$
a^{p-1} \equiv 1 \pmod {p}
$$

因此，

$$
\begin{aligned}
ax&\equiv 1 &\pmod p\\
\Rightarrow ax&\equiv a^{p-1} &\pmod p\\
\Rightarrow x &\equiv a^{p-2} &\pmod p
\end{aligned}
$$

用快速幂算出 $a^{p-2} \pmod p$ 的值，这个数就是它的逆元了。

递推

用于求连续的数对于同一模数的逆元。

P3811 【模板】乘法逆元

首先有 $1^{-1}\equiv 1 \pmod p$。

然后设 $p=ki+r(1<r<i<p)$，即 $k$ 是 $\frac{p}{i}$ 的商，$r$ 是余数。

再将这个式子放到模 $p$ 意义下，有

$$
k\times i+r \equiv 0 \pmod p
$$

两边乘上 $i^{-1}r^{-1}$，有

$$
\begin{aligned}
k\times r^{-1}+i^{-1}&\equiv 0 &\pmod p\\
\Rightarrow{}i^{-1}&\equiv -k\times r^{-1} &\pmod p\\
\Rightarrow{}i^{-1}&\equiv -\lfloor \frac{p}{i} \rfloor*(p \bmod i)^{-1} &\pmod p
\end{aligned}
$$

于是，我们就可以递推求得逆元了。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

long long inv[int(3e6+10)]; int n, p;
int main() {
    
    scanf("%d%d", &n, &p);
    inv[1] = 1;
    for(int i=2; i<=n; ++i) {
        inv[i] = p-(p/i)*inv[p%i]%p;
    }
    for(int i=1; i<=n; ++i) printf("%lld\n", inv[i]);
    return 0;
}

阶乘

首先有这样一个结论：$\frac{1}{n!}=\frac{1}{n}\times\frac{1}{(n-1)!}$，即 $(n-1)!$ 的逆元等于 $n!$ 的逆元乘 $n$。

因此，我们求出 $n!$ 的逆元然后逆推，可以求出 $1!,2!,\dots,n!$ 的逆元；又 $\frac{1}{n!}\times(n-1)!=\frac{1}{n}$，$n!$ 的逆元乘上 $(n-1)!$ 可以得到 $n$ 的逆元。