线性求逆元

小知识来啦。

逆元是费马小定理的一个衍生物（算是吧），主要用于模运算中的除法运算。费马小定理是说假如有\(p\in P,lca(a,p)=1(P为质数集合)\)，那么\(a^{p-1}\equiv 1\pmod p\)。换句话说，\(a\times a^{p-2}\equiv 1\pmod p\)。于是我们就会发现\(a^{p-2}\pmod p\)就是逆元。

普通状态下我们可以用 \(O(log p)\)的快速幂求解，但有些时候题目要求线性求解（比如p到达\(10^6\)级别）时，就要用线性求逆元的方法了。

可以推一下公式：

假设inv为逆元函数（关于模数p），那么会有（逆元的定义）：

\[\frac{a}{b}\equiv a\times inv(b)\pmod p \]

\[a\times inv(a)\equiv 1\pmod p \]

设\(t=\lfloor\frac{p}{i}\rfloor,k=p\%i\)，那么，

\[t\times i+k\equiv p\equiv 0\pmod p \]

\[-t\times i\equiv k\pmod p \]

\[-t\times i\times inv(i)\times inv(k)\equiv k\times inv(i)\times inv(k)\pmod p \]

\[-t\times inv(k)\equiv inv(i)\pmod p \]

又因为：

\[-t\equiv -\lfloor\frac{p}{i}\rfloor\equiv p-\lfloor\frac{p}{i}\rfloor\pmod p \]

结果就是：

\[inv(i)=(p-\lfloor\frac{p}{i}\rfloor)\times inv(p\%i)\%p \]

于是就可以线性求解了。