乘法逆元

发表于 更新于 分类于 阅读次数：

小学奥数都还给老师了… 对于$a$，且$a,p$互质，称$a \times x \equiv 1 \pmod p$中的$x$为$a$的逆元，记为$a^{-1}$ 文中数字默认都是正整数

费马小定理

我们都知道，若$p$为素数，有$a^{p} \equiv a \pmod p$ 若$a$不是$p$的倍数，则$a^{p-1} \equiv 1 \pmod p$ 所以$a \times x \equiv a^{p-1}$，$x \equiv a^{p-2}$ 直接上快速幂求$a^{p-2} \pmod p$即可

扩展欧几里得

要求$a \times x \equiv 1 \pmod p$，即求$a \times x + p \times y = 1$ 扩展欧几里得貌似跑的比快速幂快一些

线性递推

设$p = k \times i + j$，则有$k \times i + j \equiv 0 \pmod p$ 给左边乘上$i^{-1},j^{-1}$，由于$x \times x^{-1} = 1$，可化为$k \times j^{-1} + i ^{-1} \equiv 0 \pmod p$ $i^{-1} \equiv -k \times j^{-1} \pmod p$ 要把答案限制在范围内，可以通过$(x \% p+p) \% p$，此处不需要外面的取模 开数组储存值，得$a[i] = p-p/i \times a[p \% i] \% p$ 注意$a[1]=1$

1
2
3
4
5
6
a[1] = 1;
cout << 1 << endl;
for (int i = 2; i <= n; ++i) {
    a[i] = p - p / i * a[p % i] % p;
    cout << a[i] << endl;
}

阶乘逆元

$i! \times (i+1) \times a[i+1] \equiv 1 \pmod p$ $a[i] \equiv (i+1) \times a[i+1] \pmod p$ 倒着递推即可 Update 19.8.23：

离线求逆元

黑科技。。 给定一组数$a_1,a_2…$，求逆元$b_1,b_2…$ 利用了一个前缀积的逆元是逆元的前缀积的思想。 构造前缀积$s_i$ $$s_n=\prod_{i=1}^na_i$$ $$\frac{1}{s_n}=\prod_{i=1}^n\frac{1}{a_i}$$ $$\frac{1}{s_{i-1}}=\frac{1}{s_i}a_i$$ $$\frac{1}{a_i}=s_{i-1}\frac{1}{s_i}$$