乘法逆元

基础概念

在数论中， 如果ab ≡ 1（mod p）, 即 p | (ab-1)（|是整除的意思）我们就说 a 和 b 在模 p 意义下互为乘法逆元, 记做 a = inv(b).
逆元有什么用呢？我们常常遇到一些题目要求结果对一个大质数 p 取模，这是因为答案很大，出题人为了不麻烦大家写高精，就采取这样的方法。加减法和乘法对取模运算都是封闭的，所以你可以处处取模来避免溢出。但遇到除法时，就麻烦了。

（12 / 3） % 4 ≠ (12%4 / 3%4) % 4

为了解决模意义下的除法问题，我们引入了逆元。 inv(a) 其实可以看做模 p 意义下的 $$a^{-1}$$ ，那么在模 p 意义下， $$\frac{a}{b}$$ 就可以变形为 a*inv(b) % p 。
实际上在模 10 意义下 inv(3)=7 ，所以上面的式子可以这样计算：

(12 / 3) % 4 = (12inv(3)) % 4 = (127) % 4 = 4

显然结果是正确的

求解方法

1.扩展欧几里得求逆

如果你还不会扩欧，那可以看下这篇博客。 因为ax ≡ 1（mod p）等价于ax+by = 1, 那么就可以通过扩欧来求解x，复杂度O(logp)由此我们还可以得出逆元存在的冲要条件是gcd(a,p) = 1。

2.费马小定理求逆

注意，这种求逆元的方法仅使用在 p 为质数的时候

费马小定理：若 p 为质数，且整数 a 满足 gcd(a,p) = 1 ，则有 $$a^{p-1}$$ ≡ 1 (mod p), 又因为ab ≡ c (mod p) 等价于 ((a%p)b) ≡ c (mod p),（这个可以自己写下式子模拟下就清楚了），所以a在模p意义下的逆元即为$$a^{p-2}$$%p，用快速幂求解即可。
一道例题有理数取余, 这道题可以加深你对分数取余的 理解，请仔细体会其与除法取余的区别。

3.线性求逆

基于拓展欧几里得算法，我们虽然可以在 O(nlogp) 时间内，求出 [1,n] (1 <= n < p) 中所有整数在模质数 [公式] 下的乘法逆元，但在面对更大的数据范围时，我们就需要更快的方法。
注意，这种求逆元的方法仅使用在 p 为质数的时候。因为难免出现[1,n]内存在数x使gcd(x,p) ≠ 1, 那么它自然就不存在模p意义下的逆元，而后面的逆元都是根据前面求出的逆元得来的，这将导致后面一连串的逆元都是错的。
我们设p = ki + r,(r < i, 1 < i < p), 将其转换为同余方程得到：

ki + r ≡ 0 (mod p)

两边同乘以$$i^{-1}$$和$$r^{-1}$$,得：

k$$r^{-1}$$ + $$i^{-1}$$ = 0 (mod p)

移项得:

$$i^{-1}$$ = -k$$r^{-1}$$ (mod p)

将 k = $$\lfloor \frac{p}{i} \rfloor$$, r = p%i代入得：

$$i^{-1}$$ = -$$\lfloor \frac{p}{i} \rfloor$$*$$(p%i)^{-1}$$ (mod p)

注意-$$\lfloor \frac{p}{i} \rfloor$$为负数，在模p意义下，其等价于p-$$\lfloor \frac{p}{i} \rfloor$$, 故有递推式：

$$i^{-1}$$ = (p-$\lfloor \frac{p}{i} \rfloor$)*$(p%i)^{-1}$ (mod p)

复杂度O(n)，模板题

4.离线逆元

其用于求解给定n个数在模p下的乘法逆元，这时递推式不再适用，时间空间都会爆炸。因为该算法并不常用，因此在此不再赘述，有兴趣的可以参考这道题，题解讲的十分清楚。

注：本篇内容借鉴于洛谷日报