本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-30 10:21:52

看完了数学一本通的线性逆元，再自行推导一下。
记 $a$ 的逆元为 $a^{-1}$
已知：$1^{-1} \equiv 1 \pmod p$
设 $k = \lfloor \frac{p}{i}\rfloor,r = p \bmod i,p = k \cdot i + r$
$k \cdot i + r \equiv 0 \pmod p$
$(k \cdot i + r) \cdot i^{-1} \cdot r^{-1} \equiv 0 \pmod p$
$k \cdot i \cdot i^{-1} \cdot r^{-1} + r \cdot i^{-1} \cdot r^{-1} \equiv 0 \pmod p$
$k \cdot r^{-1} + i^{-1} \equiv 0 \pmod p$
$i^{-1} \equiv -k \cdot r^{-1} \pmod p$
$i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} \pmod p$

总体推导思路：先将 $p $用已知量表示出来，然后通过乘上一些数使得这个式子的其中一项为要求的逆元（$i^{-1}$），然后移项得到结果。