自行学习用

如果是$p$是质数，则存在一个线性的逆元
我们假设$inv[a]$表示$a$的逆元
则存在$inv(a) = (p - p / a) * inv(p \% a) \% p$

证明：

设 $ x = p \% a, y = p / a $
-> $ x + y * a = p$
-> $ (x + y * a) \% p = 0 $
-> $ x \% p = (-y) * a \% p $
-> $ x * inv(a) \% p = (-y) \% p $
-> $ inv(a) = (-y) * inv(x) \% p $
-> $ inv(a) = (-y + p) * inv(x) \% p $
-> $ inv(a) = (p - p / a) * inv(p \% a) \% p $