我们这里讨论关于取模运算的乘法逆元。
定义：
所以逆元有什么用呢？
题目中可能会出现操作中间树很大的情况，如求解：
规定中间变量不能超过7，于是操作步骤为：
发现无法整除。
可以求出除数3关于模数7的逆元为5，根据定义，在7模数下，3 * 5 = 1，所以1/3 = 5.
于是问题来到了如何求逆元。
费马小定理：
改写一下：
最后更新于2年前
数学上乘法逆元的定义是 ax=1，则x是a的乘法逆元ax=1，则x是a的乘法逆元ax=1，则x是a的乘法逆元。
满足 axmod b=1ax\mod b = 1axmodb=1时，称 x为a关于模b的逆元x为a关于模b的逆元x为a关于模b的逆元。
3∗6/3mod 73 * 6 / 3 \mod 73∗6/3mod7
原式=((3∗6)mod 7)/3mod 7原式 = ((3*6)\mod 7)/3 \mod 7原式=((3∗6)mod7)/3mod7
=4/3= 4/3=4/3
于是我们可以把/3/3/3替换成555，避免了无法整除的问题。
ab−1mod b=1a^{b-1} \mod b = 1ab−1modb=1
ab−2∗amod b=1a^{b-2} * a\mod b = 1ab−2∗amodb=1
所以 ab−2a^{b-2}ab−2 就是a模b的逆元。一般这个数用快速幂来算。
