逆元(Inverse element)就是在mod意义下，不能直接除以一个数，而要乘以它的逆元。 比如 a ∗ b ≡ 1 ( m o d p ) a*b≡1 (mod p) a∗b≡1(modp)，那么a，b互为模n意义下的逆元，比如你要算x/a，就可以改成x*b%p

观察 a ∗ b ≡ 1 ( m o d p ) a*b≡1 (mod p) a∗b≡1(modp),变形为 a ∗ b + k ∗ p = 1 a*b + k*p =1 a∗b+k∗p=1，就可以用扩展欧几里得算法求a了，同时这里也说明了a和p只有在互素的情况下才存在逆元。

在下面所有的算法中，最好先把除数取个模再运算。

a ∗ b ≡ 1 ( m o d p ) a*b≡1 (mod p) a∗b≡1(modp) a ∗ b + k ∗ p = 1 a*b + k*p =1 a∗b+k∗p=1 然后a就是我们要求的逆元，最终得到一个正数a的话就要对a mod p，因为a加上mp的时侯k减少mb可以使得等式依然成立。

如果你不想让逆元为正数，那么直接返回x也是可以正确的逆元

注意：返回的时候可以改成(x+mod)%mod，因为扩展欧几里得算法算出来的x应该不会太大.

性能分析:

费马小定理：若p为素数，则有 a p − 1 ≡ 1 ( m o d p ) a^{p-1}≡1(mod p) ap−1≡1(modp) a p − 2 ∗ a ≡ 1 ( m o d p ) a^{p-2}*a≡1(mod p) ap−2∗a≡1(modp) a p − 2 a^{p-2} ap−2就是a在mod p意义下的逆元啦。

欧拉定理：若a、p互素，则有 a φ ( p ) ≡ 1 ( m o d p ) a^{φ(p)}≡1(mod p) aφ(p)≡1(modp)(费马小定理的一般形式) a φ ( p ) ∗ a ≡ 1 ( m o d p ) a^{φ(p)}*a≡1(mod p) aφ(p)∗a≡1(modp) a φ ( p ) − 1 a^{φ(p)-1} aφ(p)−1就是a在mod p意义下的逆元啦。

性能分析：

p是模数，i是待求的逆元，我们求的是 i − 1 i^{-1} i−1在mod p意义下的值 p = k ∗ i + r p=k*i+r p=k∗i+r令 r < i,则k=p/i,r=p%i k ∗ i + r ≡ 0 ( m o d p ) k*i+r≡0(mod p) k∗i+r≡0(modp) k ∗ r − 1 + i − 1 ≡ 0 ( m o d p ) k*r^{-1}+i^{-1}≡0(mod p) k∗r−1+i−1≡0(modp) i − 1 ≡ − k ∗ r − 1 ( m o d p ) i^{-1}≡-k*r^{-1}(mod p) i−1≡−k∗r−1(modp) i − 1 ≡ − p / i ∗ i n v [ p m o d i ] i^{-1}≡-p/i*inv[p mod i ] i−1≡−p/i∗inv[pmodi] 嗯。。好难看的公式 说白了就是:inv[i]=-(mod/i)*inv[mod%i] 然后边界是inv[1]=1 这不仅为我们提供了一个线性求逆元的方法，也提供了一种O(logmod)求逆元的方法