数论

同余

$$ a \equiv b \pmod{p} \iff a % p = b % p $$

即
$a - b \equiv 0 \pmod{p}$

逆元
$a * b \equiv 1 \pmod{p} $
定义 a 和 b 互为逆元，也就是说 $a \equiv \frac{1}{b} \pmod{p} $

除法的模 $\frac{a}{b} \pmod{p}$ 看成$a$ 乘 $b$的逆元

s $a * \frac{1}{b} \pmod{p}$

根据费马小定理 求逆元：

要求 $p$ 是质数且 $p$ 和 $a$ 互质

$$ a^{p-1} \equiv 1 \pmod{p} \implies \frac{1}{a} \equiv a^{p-2} \pmod{p} $$