## 逆元定义 设c是b的逆元，则有b\*c≡1(mod m)； ## 逆元使用 假设求(a/b)%m,由于b的值可能会很大，导致结果精度损失，因此我们需要做如下变换： ~~~[math] (a/b)%m=(a/b)\*1%m=(a/b)\*b\*c%m=a*c%m ~~~ 这样，我们就能把一个小数表示成整数的形式了，而且精度也不会有任何损失。 这就是逆元的作用。 ## 逆元求解 对于上面例子，我们如何求出c的值呢？这里就用到了费马小定理。 根据费马小定理b^(m-1)≡1(mod m),而b*c≡1(mod m),因此，c=b^(m-2)%m。这样，我们就能求出c的值了。由于m的值可能会非常大，因此我们也需要使用快速幂来求解。 int m; int inv(int b){//Inverse element 逆元素（逆元） int res=1; int x=m-2; while(x){ if(x&1) res=res*b%m; b=b*b%m; x>>=1; } return res; } 这就是求解逆元的一般方法。