我们目标是求i模p下的逆元。
首先有[latex]1 \times 1^{-1} \equiv 1 \pmod{p}[/latex]
设[latex]ki+d = p[/latex], 那么有[latex]ki+d \equiv 0 \pmod{p}[/latex]
继续推导, 两边同时乘以[latex]i^{-1}d^{-1}[/latex]:[latex]k d^{-1} + i^{-1} \equiv 0 \pmod{p}[/latex]
移项:[latex]i^{-1} \equiv -k d^{-1} \pmod{p}[/latex]
把k和d换掉: [latex]i^{-1} \equiv – \lfloor \frac{p}{i} \rfloor (p \mod i)^{-1} \pmod{p}[/latex]
假设小于i的逆元已经全部处理出来了, 那么这个就可以直接筛了…
代码超短:
inverse[i] = (LL)-p/i*inverse[p%i]%p;
Join the discussion