逆元
一、什么是逆元?  如果存在一个最小的正整数的解x使得：ax≡1（mod m）；那么称作x是a的逆元。
二、求逆元有什么用处呢？ 在有除法的取模运算：（b/a）%m中，对于取模运算中，+ - *是没有错误的，所以直接相除再取模的结果不一定就是正确的。 如果我们此时有a的逆元，那么结果就是：（b*a的逆元）%m； 将除法很巧妙的变成了乘法。
三、那么我们如何求逆元呢？ 求解逆元的过程其实并不难，通常我们用拓展欧几里得算法来求逆元。 对于：ax≡1（mod m） 我们根据数学的基础知识不难将其转化为：ax=1+k*m（这里k是一个>=0的整数）； 那么就有：ax-k*m=1；那么求解这个x我们就可以用拓展欧几里得算法来求得。 从上式我们也不难理解，想要求a的逆元，需要满足：gcd（a，m）==1；
四、如果m不是素数，我们除法取模可以写成这样：

五、实现代码：

int ex_gcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int ans=ex_gcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; return ans; } int mod_inverse(int a,int m) { int x,y; ex_gcd(a,m,x,y); return (x%m+m)%m;//如果直接求解出来的x是一个负数，那么显然我们要将其转化成正数。 }