数学笔记：逆元
逆元
一整数a对同余n之模逆元是满足以下公式的整数b
[latex display=”true”] a^{-1} \equiv b \pmod{n} [/latex]
也可以写成
[latex display=”true”] ab \equiv 1 \pmod{n} [/latex]
求逆元的方法
扩展欧几里得算法
费马小定理
费马小定理可以转换成如下形式
若a是一个整数，p是一个质数，则
[latex display=”true”]a^{p-2} \equiv a^{-1} \pmod{p}[/latex]
线性递推
我们设[latex]p=ki+r, r < i, 1 < i < p[/latex]，然后把左边的式子展开
[latex display=”true”]ki + r \equiv 0 \pmod{p}[/latex]
两边同乘[latex] (ir)^{-1} [/latex]
[latex display=”true”]\begin{aligned} kr^{-1} + i^{-1} &\equiv 0 &\pmod{p} \\ i^{-1} &\equiv -kr^{-1} &\pmod{p} \\ i^{-1} &\equiv -\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} &\pmod{p} \end{aligned}[/latex]
于是我们就得到了逆元的线性递推式：
inv[i] = -(MO / i) * inv[MO % i];
阶乘的逆元
先处理[latex] (n!)^{-1} [/latex]，然后[latex] [(n-1)!]^{-1} \equiv n(n!)^{-1} \pmod{p} [/latex]。
