逆元定义
如果 \(ax\equiv 1\pmod p\)，则称 \(x\) 为 \(a\) 在模 \(p\) 意义下的乘法逆元。
逆元存在当且仅当 \(a\perp p\)，即 \(\gcd(a,p)=1\)。
将 \(ax\equiv 1\pmod p\) 转化可得 \(x\equiv\dfrac{1}{a}\pmod p\)，那么模意义下 \(t \div a\) 就相当于 \(t \times x\)。
快速求单个数的逆元
快速幂
费马小定理
当 \(p\nmid a\) 且 \(p\in\mathbb{P}\) 时，有
\[a^{p-1}\equiv 1\pmod p \]
由此转化可得 \(a\times a^{p-2}\equiv 1\pmod p\)，此时就可以发现 \(a^{p-2}\) 即为 \(a\) 在模 \(p\) 意义下的乘法逆元。
此时可以用快速幂计算逆元，时间复杂度 \(O(\log p)\)。
扩展欧几里得算法
\(\text{Exgcd}\) 也可以用于求逆元。
由裴蜀定理可知，若 \(a\perp p\)，则必然 \(\exists \, y\)，使得 \(a\times x+p\times y=1\) 成立。
容易发现，\(a\times x+p\times y=1\Leftrightarrow a\times x\equiv 1\pmod p\)。
使用 \(\text{exgcd}\) 解出这个方程即可，时间复杂度 \(O(\log p)\)。
线性求 \(1\sim n\) 的逆元
例题：loj #110. 乘法逆元。
现要求在 \(O(n)\) 的时间内，求出模 \(m\) 的意义下，\([1,m)\) 中所有数的乘法逆元。
容易发现，\(\forall\, m\in\mathbb{Z}\)，有 \(1 \times 1 \equiv 1\pmod m\)，所以 \(1\) 的逆元恒为 \(1\)。
考虑 递推。
假设我们已知 \([1,x)\) 内所有数的逆元，需要求出 \(x\) 的逆元。
将模数 \(m\) 表示为 \(kx+t\)，其中 \(k=\Big\lfloor\dfrac{m}{x}\Big\rfloor\)，\(t=m\bmod x\)。
由此可得 \(kx+t\equiv 0\pmod m\)。
两边同乘 \(x^{-1}\times t^{-1}\pmod m\)，可得
\[\begin{aligned} kx\times x^{-1}\times t^{-1}+t\times x^{-1}\times t^{-1}\equiv 0\pmod m\\ k\times t^{-1}+x^{-1}\equiv 0\pmod m\\ \end{aligned} \]即可得 \(x^{-1}\equiv k\times t^{-1}\pmod m\)。
在此基础上代入 \(k=\Big\lfloor\dfrac{m}{x}\Big\rfloor\)，\(t=m\bmod x\)，可得
\[x^{-1} \equiv -\Big\lfloor\dfrac{m}{x}\Big\rfloor(m\bmod x)^{-1}\pmod m \]由于 \((m\bmod x)^{-1}\in[1,x)\)，所以 \((m\bmod x)^{-1}\) 已知，线性递推即可。
- \(\textbf{PS 1}\)：当 \(m\bmod x=0\) 时 \(x\) 不存在模 \(m\) 意义下的乘法逆元。
- \(\textbf{PS 2}\)：由于 \(\text{C++}\) 中负数取模的结果为负数，所以在实际实现时递推式应写为
(m - m / x) * inv[m % x] % m。
综上所述，递推式即为：
\[x^{-1}= \begin{cases} 1&x=1\\ -\Big\lfloor\dfrac{m}{x}\Big\rfloor(m\bmod x)^{-1}&x\not=1 \end{cases} \pmod m \]线性递推即可在 \(O(n)\) 的时间内完成。
线性求任意 \(n\) 个数的逆元
例题：loj #161 乘法逆元 2。
显然，对于每一个数用 快速幂 / \(\text{exgcd}\) 求解，时间复杂度为 \(O(n\log p)\)，无法通过本题。
考虑使用前缀积 \(\{s_n\}\)，其中 \(s_i\) 记录 \(\prod_{j=1}^{i}a_j\)。
此外需要前缀积的逆元，使用 \(\{t_n\}\) 序列，其中 \(t_i=s_{i}^{-1}\pmod p\)。
接下来可以通过 快速幂 / \(\text{exgcd}\) 求解 \(s_n\) 的逆元，记为 \(t_n\)。
接下来可以通过如下公式线性递推求出 \(\{t_n\}\)：
\[t_i \equiv s_i^{-1} \equiv \dfrac{1}{\prod_{j=1}^{i}a_j} \equiv \dfrac{a_{i+1}}{\prod_{j=1}^{i+1}{a_j}} \equiv a_{i+1}\times s_{i+1}^{-1} \equiv a_{i+1}\times t_{i+1}\pmod p \]记原序列的逆元为 \(\{\text{inv}_n\}\)，其中 \(\text{inv}_i=a_{i}^{-1}\pmod p\)。
由于已知前缀积数组的逆元，那么
\[\text{inv}_i \equiv a_{i}^{-1} \equiv \dfrac{1}{a_i} \equiv \dfrac{1}{\dfrac{s_i}{s_{i-1}}} \equiv \dfrac{s_{i-1}}{s_i} \equiv s_{i-1}\times t_{i} \]故递推即可，时间复杂度为 \(O(n+\log p)\)，其中 \(O(\log p)\) 是求 \(s_n\) 逆元的复杂度。
标签：pmod,dfrac,times,逆元,text,乘法,equiv From： https://www.cnblogs.com/oier-wst/p/18423863/mul_inv