其实这篇博客只是搬运一下我之前（大概是NOIP那会）写在word里的笔记…
下面直接复制原话，题目是洛谷上求逆元的模板题：https://www.luogu.org/problemnew/show/P3811
我一开始只知道这题的两种方法… 首先我们知道逆元可以用 exgcd 求，但是复杂度是$O(nlogn)$…在这会被卡掉
注意到$p$是质数那么根据费马小定理： $a^{p−1} equiv 1pmod p,a ot p $在这里进一步得到：
$a ∗ a^{p−2} equiv 1pmod p $
然后$a$在模质数$p$的意义下的逆元就是$a^{p−2}mod p$
但是这样子复杂度但还是没变…过不去…
注意到这里是要求$1$~$n$范围内模$p$的逆元，考虑线性递推？
于是找到一篇不错的博客：http://blog.miskcoo.com/2014/09/linear-find-all-invert
大概意思就是把$p$写成$p=k*i +r,(k = lfloor frac{p}{i}
floor,r=p mod i)$，根据取模运算的定义显然是正确的。
这样，然后两边对$p$取模：
$k ∗ i + r equiv 0 pmod p $
同乘$i^{−1},r^{−1}$：
$k ∗ r^{−1} + i^{−1} equiv 0 pmod p$
$i^{−1} equiv −lfloor frac{p}{i}
floor*(pmod i)^{-1} pmod p$
这样一来加上$1^{−1} equiv 1pmod p$就可以线性递推这个东西了~
写起来就一句话：
inv[i]=((-p/i*inv[p%i])%p+p)%p
顺便放上三种求法的代码：