线性递推求1~n的逆元 学习笔记
题意
求\(1\sim n\)中所有整数在模\(p\)意义下的乘法逆元。
题解
设\(a=\left\lfloor\frac{P}{i}\right\rfloor,b=P\bmod i\)，则\(ai+b=P\)
即\(ai+b\equiv 0 \pmod P\)
\[\begin{align*} &\therefore \frac{ai+b}{ib}\equiv 0 \pmod P \\ &\therefore ab^{-1}+i^{-1}\equiv 0 \pmod P \\ &\therefore\ i^{-1}\equiv -ab^{-1} \pmod P \end{align*}\]
即\[inv(i)=\left(P-\left\lfloor\frac{P}{i}\right\rfloor\right)\cdot inv(P\bmod i)\bmod P\]
于是\(O(n)\)递推求一下就可以了。
代码
1 |
|
