乘法逆元在哪本书上?怎么运算?求大神赐教!

更新时间2019-04-19 05:21:19

乘法逆元是数论中重要的内容，也是 ACM 中常用到的数论算法之一。乘法逆元小结

在求解除法取模问题(a/b)%m时，我们可以转化为(a%(b∗m))/b，
但是如果b很大，则会出现爆精度问题，所以我们避免使用除法直接计算。
可以使用逆元将除法转换为乘法：
假设b存在乘法逆元，即与m互质（充要条件）。设c是b的逆元，即b∗c≡1(modm)，那么有a/b=(a/b)∗1=(a/b)∗b∗c=a∗c(modm)
即，除以一个数取模等于乘以这个数的逆元取模。逆元求解一般利用扩欧。当m为质数的时候直接使用费马小定理，m非质数使用欧拉函数。当m为质数的时候，神奇的线性方法。