什么叫乘法逆元？
这里，我们称 x 是 a 关于 m 的乘法逆元
这怎么求？可以等价于这样的表达式： a*x + m*y = 1
怎么求逆元？
1，扩展欧几里德算法求逆元
int ex_gcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } int ans=ex_gcd(b,a%b,y,x); y-=a/b*x; return ans; } int inv(int a,int mod){ int x,y; int ans=ex_gcd(a,mod,x,y); if(ans==1) return (x%n+n)%n; return -1; }
原文：http://www.cnblogs.com/L-King/p/5714592.html