乘法逆元

---

数学上乘法逆元的定义是 $ax=1，则x是a的乘法逆元$。

我们这里讨论关于取模运算的乘法逆元。

定义：

满足 $ax\mod b = 1$时，称 $x为a关于模b的逆元$。

所以逆元有什么用呢？

题目中可能会出现操作中间树很大的情况，如求解：

$3 * 6 / 3 \mod 7$

规定中间变量不能超过7，于是操作步骤为：

$原式 = ((3*6)\mod 7)/3 \mod 7$

$= 4/3$

发现无法整除。

可以求出除数3关于模数7的逆元为5，根据定义，在7模数下，3 * 5 = 1，所以1/3 = 5.

于是我们可以把$/3$替换成$5$，避免了无法整除的问题。

于是问题来到了如何求逆元。

费马小定理：

$a^{b-1} \mod b = 1$

改写一下：

$a^{b-2} * a\mod b = 1$

所以 $a^{b-2}$ 就是a模b的逆元。一般这个数用快速幂来算。