定义
当 \(a,b\) 满足 \(ab \equiv 1\pmod p\) ，\(a,b\) 互为 \(\pmod p\) 的乘法逆元，也记作 \(a^{-1}\) 和 \(b^{-1}\) 。
前置知识
1.费马小定理
若 \(p\) 为质数且 \(\gcd(a,p) = 1\) ，则 \(a, p\) 满足 \(a^{p-1}\equiv 1 \pmod p\) 。
证明:
考虑下面两个整数序列：
\[1,2,3,4,5......p-2,p-1 \]\[a,2a,3a,4a,5a.......(p-2)a,(p-1)a \]第一个序列很明显每个数对 \(p\) 取余各不相同，且为 \(1\) 到 \(p-1\) 。
对于第二个序列，如果有两个不同的数 \(ax\) ，\(ay\) 使得 \(ax\equiv ay \pmod p\) ，则 \(p|a|x-y|\) 。
\(\because\) \(\gcd(a,p)=1\) , \(\therefore\) \(p||x-y|\) 。
又 \(\because\) \(x,y < p\) 且 \(x \not= y\) ， \(\therefore\) \(0<|x-y|<p\) ，\(p \not| \,|x-y|\) ，矛盾。
\(\therefore\) 第二个序列每个数对 \(p\) 取余都不相同, 且不为 \(0\) 。
\(\therefore\) 第二个序列中 \(p-1\) 个数对 \(p\) 取模为 \(1\) 到 \(p-1\) 各一个。
现在把第一个序列的数和第二个序列的数各自相乘，得到：
\[(p-1)!\equiv a^{p-1}(p-1)! \pmod p \]\(\because\) \((p-1)!\) 与 \(p\) 互质。\(\therefore\) 可以把两边同时除以 \((p-1)!\) 得到：
\[a^{p-1}\equiv 1\pmod p \]得证。
2.欧拉定理
若 \(a,p\) 满足 \(\gcd(a,p)=1\) ，则 \(a^{\phi(p)}\equiv 1 \pmod p\) 。当 \(p\) 是质数时，欧拉定理等价与费马小定理。
证明：
与上面类似，考虑下面两个整数序列：
\[x_1,x_2,x_3,x_4,x_5......x_{\phi(p)-1},x_{\phi(p)} \]\[ax_1,ax_2,ax_3,ax_4,ax_5.......ax_{\phi(p)-1},ax_{\phi(p)} \]第一个序列是模 \(p\) 意义下的一个简化剩余系，则第二个序列也为模 \(p\) 意义下的一个简化剩余系，把两个序列的数各自相乘得到：
\[\prod_{i=1}^{\phi(p)}x_i\equiv a^{\phi(p)} \times \prod_{i=1}^{\phi(p)}x_i \pmod p \]\(\because\) \(\prod_{i=1}^{\phi(p)}x_i\) 与 \(p\) 互质。\(\therefore\) 可以把两边同时除以 \((p-1)!\) 得到：
\[a^{\phi(p)}\equiv1\pmod p \]得证。
如何求逆元
我们现在要求 \(a\) 在 \(\bmod \,p\) 意义下的逆元，即方程 \(ax\equiv 1 \pmod p\) 的解。
1.当 \(p\) 是质数且 \(\gcd(a,p)=1\) 时，根据费马小定理可得：
\[a^{p-1}\equiv 1 \pmod p \]\[a \times a^{p-2} \equiv 1\pmod p \]\(\therefore\) \(a\) 的逆元就是 \(a^{p-2}\) ，可以用快速幂求，时间复杂度 \(O(\log p)\) 。
2.当 \(\gcd(a,p)=1\) 时，根据欧拉定理可得：
\[a^{\phi(p)}\equiv 1 \pmod p \]\[a \times a^{\phi(p)-1} \equiv 1\pmod p \]\(\therefore\) \(a\) 的逆元就是 \(a^{\phi(p)-1}\)，其中欧拉函数 \(\phi\) 可以在 \(O(\sqrt p)\) 的时间算出来(不过好像也有一些玄学的算法，但 \(p\) 的范围一般不会爆 int ，所以这也够了)， 而快速幂的时间是 \(O(\log p)\) 。
逆元的作用
我们知道，余数有可加性，可减性，可乘性，但没有可除性，当要对分数取模时，逆元就派上用场。
分数 \(\dfrac{a}{b}\) 对 \(p\) 取模的结果相当于 \(a \times b^{-1}\pmod p\) ,也就是分子乘上分母在模 \(p\) 意义下的逆元，这样就可以对分数取模了。
注意，求逆元的时间复杂度是 \(O(\log p)\) ，所以求逆元的次数越少越好。
线性求逆元
有时候我们需要以 \(O(n)\) 的复杂度求出 \(1\) 到 \(n\) 所有数在模 \(p\) 意义下的逆元，这时候一个一个求的复杂度就变为 \(O(n \log p)\) 了，我们需要用别的方法 \(O(n)\) 的求逆元。
以 P3811 【模板】乘法逆元 为例
题目要求求出 \(1\) 到 \(n\) 所有数在模 \(p\) 意义下的逆元，我们考虑如何递推逆元。
设我们当前正在求 \(a\) 的逆元，并且已经求出 \(1\) 到 \(a-1\) 的逆元，现在要以 \(O(1)\) 的时间复杂度推出 \(a\) 的逆元。我们可以做一个带余除法：
\[p \div a = b ......r \]变成等式：
\[a \times b + r = p \]这个式子在模 \(p\) 意义下变为：
\[a \times b + r \equiv 0 \pmod p \]而 \(r < a\) ，所以我们已经知道 \(r^{-1}\) ，现在我们给式子乘上一个 \(a^{-1}r^{-1}\) ：
\[a \times b \times a^{-1} \times r ^{-1} + r \times r^{-1} \times a^{-1}\ \equiv 0 \pmod p \]\(a\) 与 \(a^{-1}\) 和 \(r\) 与 \(r^{-1}\) 相乘都变成 \(1\) ，所以:
\[b \times r^{-1} + a^{-1} \equiv 0 \pmod p \]\[a^{-1} \equiv -b \times r^{-1} \pmod p \]这样我们就推出了 \(a\) 的逆元，总时间复杂度 \(O(n)\) 。
阶乘逆元
组合数的公式是 \(C_n^m = \frac{n!}{m!(n-m)!}\) ，当我们需要对一个组合数取模，必须先把组合数算出来再取模，而算的过程中是无法取模的，但阶乘又很大，所以我们就需要用到阶乘的逆元。阶乘的逆元也可以 \(O(n)\) 的递推，但是是倒着推。
设我们当前正在求 \(k!\) 的逆元，已经求出了 \((k+1)!\) 到 \(n!\) 的逆元，我们知道：
\[(k+1)![(k+1)!]^{-1} \equiv 1 \pmod p \]把 \((k+1)!\) 拆成 \(k!\) 和 \((k+1)\)，可得：
\[k! \times (k+1)[(k+1)!]^{-1}\equiv 1 \pmod p \]\(\therefore\) \((k!)^{-1}=(k+1)[(k+1)!]^{-1}\) ，然后我们就可以 \(O(n)\) 的递推了，但是首先我们要求出 \(n!\) ，这就可以用费马小定理或者欧拉定理直接求即可。
一些题目
题意：给你 \(3\) 个数 \(n,p,k\) 和一个长度为 \(n\) 序列 \(a\) ，求出
\(\sum_{i=1}^n\frac{k^i}{a_i}\)
对 \(p\) 取模的值。
思路：
朴素的求每一项的值时间复杂度是 \(O(n \log p)\) 的，而 \(n,p\) 都很大，而且这题卡的很死，所以考虑如何优化。
为了减少求逆元的次数，我们可以直接通分，然后就变成了下面这个样子：
\[\frac{\sum_{i=1}^{n}{(k^i\times\prod^{i-1}_{j=1}a_i\times\prod_{j=i+1}^na_i})}{\prod_{i=1}^na_i} \]这样我们就可以我们可以先计算出分子和分母，再求一次逆元即可。我们可以 \(O(n)\) 的求出 \(a\) 的前缀积和后缀积以及 \(k\) 的幂次方，最后统计答案即可，时间复杂度 \(O(n + \log p)=O(n)\) 。
标签：phi,pmod,笔记,times,逆元,ax,乘法,equiv From： https://www.cnblogs.com/rlc202204/p/16949458.html