当前位置 博文首页 > Hi_jiaxinwei的博客:【逆元】
逆元(inv)
1.什么是逆元
当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法:
设c是b的逆元,则有b*c≡1(mod m);
则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);
即a/b的模等于a*b的逆元的模;
逆元就是这样应用的;
2.求逆元的方法
(1).费马小定理
在?
p?
是素数的情况下,对任意整数?
x?
都有?
xp≡x(mod)p?
。?
如果?
x?
无法被?
p?
整除,则有?
xp?1≡1(modp)?
。?
可以在?
p?
为素数的情况下求出一个数的逆元,?