版权声明：本文为博主原创文章遵循 版权协议，转载请附上原文出处链接和本声明
逆元(Inverse element)就是在mod意义下，不能直接除以一个数而要乘以它的逆元。
比如a?b≡1(modp)a?b≡1(modp)那么a，b互为模n意义下的逆元比如你要算x/a，就可以改成x*b%p
观察a?b≡1(modp)a?b≡1(modp)就可以用扩展欧几里得算法求a了，同时这里也说明了a和p只有茬互素的情况下才存在逆元
在下面所有的算法中，最好先把除数取个模再运算
方法一：扩展欧几里得算法
然后a就是我们要求的逆元，最终得到一个正数a的话就要对a mod p因为a加上mp的时侯k减少mb可以使得等式依然成立。
如果你不想让逆元为正数那么直接返回x也是可以正确的逆元
注意：返回的时候可以改成(x+mod)%mod，因为扩展欧几里得算法算出来的x应该不会太大.
- 时间复杂度:O(logn)（实际是斐波那契数列）
- 适用范围：只要存在逆元即可求适用于个数不多但是mod很大的时候，也是最常见的一种求逆元的方法
方法二:费马小定理/欧拉定理
- 适用范围：一般在mod是个素数的时候用，比扩欧快一点而且好写
- 但是如果是合数，相信一般沒人无聊到去算个欧拉函数
p是模数，i是待求的逆元我们求的是i?1i?1
这不仅为我们提供了一个线性求逆元的方法，也提供了一种O(logmod)求逆元的方法
- 调用的时候要先对除数取mod
- 适用范围：mod数是不大的素数而且多次调用比如卢卡斯定理。
- 好像找到了最简单的算法了！！
- 适用范围： mod数是素数所以并不好用，比如中国剩余定理中就不好使因为很多时候可能会忘记考慮mod数是不是素数。
