【学习笔记 23】逆元

_Wind_Leaves_ShaDow_ · 2023-09-12 16:41:54 · 个人记录

基础知识。

逆元的定义很简单，在一个计算方式下对一个数逆运算使用的元素。比如在加法意义下 3 的逆元是 -3，因为相加后不存在。在乘法意义下 3 的逆元是 \large\frac{1}{3}，因为相乘后变成 1，在乘法意义下不存在。

如果我们要求得 (a\div b)\ mod\ p 的值，不能简单 a\ mod\ p \div b\ mod\ p。而应该将 \div b 改成 \times b^{-1}\pmod p。也就是乘以 b 的逆元。

那么如何求 b 的逆元？

• 模板

• 引理：费马小定理

对于一个质数 p，若有 a 且 a 不是 p 的倍数，则有 a^{p-1}=1\pmod p。

拆一下就是 a\times a^{p-2}=1。

代入 ax=1\pmod p，得到 x=a^{p-2}，用快速幂求得即可。

但是这样子是过不了模板题的。

• 线性求连续数字的逆元

意思就是在 O(n) 的时间内处理出 1 到 n 的逆元，如果没有即为 0。

对于 1，它的逆元即为 1。

不想打向下取整，所以下面的 p/i 代表整除。

对于 i，设 i\times k+r=p。即 k=p/i，r=p\ mod\ i。

在 \pmod p 意义下，该式转化为 i\times k+r=0\pmod p。

其中 (p\ mod\ i)^{-1} 的值已经求过（递推，p\ mod\ i 一定小于 i）。所以就这么求出来了。

inv[1]=1;
for(int i=2;i<=n;i++){
    inv[i]=(p-p/i)*inv[p%i]%p;//p-p/i 为了防止越界
}

• 线性求非连续数字的逆元

对于长度 n 的 a_1,a_2,\dots,a_n。前缀积 s_i=a_1\times a_2\times\dots\times a_i。如果我们求出 s_n的逆元 v_n， 就可以求得 v_{n-1},v_{n-2}\dots,v_1 的值。具体地，对于 v_i，v_i=v_{i+1}\times a_i。也就是 s_{i+1} 即 a_1\times a_2\times\dots\times a_{i+1} 的逆元乘 a_{i+1}，由逆元操作可以得知这里 a_{i+1} 被消掉。

于是 a_i 的逆元就是 v_i\times s_{i-1}。原理显然。

• 两种逆元方式的不同于优劣

对于快速幂（以后学了 exgcd 会有更新），求 单个数 的复杂度为 O(\log p)。明显优于 O(n)。

对于线性算法，线性的优劣很明显：对于很多的数据可以处理得很快，但对于单个数据还需要线性处理则很慢。

鸣谢