乘法逆元
什么是乘法逆元？
那么存在一个b，使得假设$gcd(a,p) = 1$,则有$a*b ≡ 1 (mod p) $ 即 $ab=pk+1$
b就叫做a关于模p的乘法逆元
怎么求乘法逆元
一.费马小定理
费马小定理：当a,p满足$gcd(a,p) = 1$ 则有$a^p≡a(modp)$
变一下形：$a⋅a ^{p-2}≡1(mod\ p)$。是不是和上面的乘法逆元的定义是相似的？
所以，我们可以使用快速幂求出$a^{p - 2}$，即求出a的逆元
二.扩展欧几里得
扩展欧几里得：找出整数对（x，y），使得$ax+by = gcd(a,b)$
$ab=pk+1$ 移项得到 $ab-pk=1$
b就对应x，-k对应y
三.递推计算阶乘的逆元
空。没看懂
乘法逆元的性质
1.存在唯一性
2.完全积性函数
把 a 的逆元表示为 inv[a]
两个数的逆元的积等于这两个数积的逆元， inv[a] * inv[b]=inv[a * b]
3.费马小定理得$a^{p-2} = 1/a(mod\ p)$
$b/a = b * a^{p-2}$ 即 b * inv[a] = b / a (mod p)
