Laffey 2022-11-02 19:56:39
就是来推个公式方便以后忘了来看
设当前要求的数为 i 在模 p 意义下的逆元。那么我们不妨设 p = k \times i + r \ (1 < r < i < p) ，则有 k \times i + r \equiv 0 \pmod {p} 。这里实际上是在设 p 除以 i 商 k 余 r 。
我们在同余式两侧同时乘上 i^{-1}, r^{-1} ，得到 k \times r^{-1} + i^{-1} \equiv 0 \pmod {p} 。
移项易得 i^{-1} \equiv -k \times r^{-1} \pmod {p} 。
将 k, r 代入，可得 i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \times (p \bmod i)^{-1} \pmod {p} 。这就是线性求逆元的递推式力。
直接按照公式代入就可以得到一个逆元的特解，通解就是所有模 p 同余的数，所以要求正整数解，只要通过取模转化成正整数就可以啦。
