什么是逆元？ 每个数a均有唯一的与之对应的乘法逆元x，使得ax≡1(mod n) ， 一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在 。
逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。 逆元的定义：定义：正整数 a, n，如果有 ax ≡ 1(mod n)，则称 x 的最小正整数解为 a 模 n的逆元。 为什么要有乘法逆元呢？ 当我们要求（a/b） mod p的值，且a很大，大到会溢出；或者说b很大，达到会爆精度。无法直接求得a/b的值时，我们就要用到乘法逆元。 求证：设k为b关于p的乘法逆元，证明(a/b)%m=(a*k)%m?
我们可以通过求b关于p的乘法逆元k，将a乘上k再模p，即(a*k) mod p。其结果与(a/b) mod p等价。
证：
根据b*k≡1 (mod p)有b*k=p*x+1。
k=(p*x+1)/b。
把k代入(a*k) mod p，得：
  (a*(p*x+1)/b) mod p
=((a*p*x)/b+a/b) mod p
=[((a*p*x)/b) mod p +(a/b)] mod p
=[(p*(a*x)/b) mod p +(a/b)] mod p
//p*[(a*x)/b] mod p=0 所以原式等于：(a/b) mod p 更简单的证明：
a/b mod p =  a* （b*b^(-1) ) /b =a*b^(-1); 乘法逆元的几种求法？ 一、循环找解法
给定模m和需要求逆的数x，直接暴力枚举1~m-1 
检查是否有x*i=1(mod m)
这种算法可以应用与写暴力、对拍、模数较小,求逆次数少的情况 
时间复杂度O(m) #include #include using namespace std; int main() { int n,m; cin>>n>>m; for(int i=1;i 二、扩展欧几里得算法
给定模数m，求a的逆元相当于求解ax=1(mod m) 
这个方程可以转化为ax-my=1 
然后套用求二元一次方程的方法，用扩展欧几里得算法求得一组x0,y0和gcd 
检查gcd是否为1 
gcd不为1则说明逆元不存在 
若为1，则调整x0到0~m-1的范围中即可 （ 用我自己的话解释一下，①：extgcd 目的 求 x ,y ； ②：逆元 目的 求 x；  ③： so 用extgcd 来求逆元 ） 一个数有逆元的充分必要条件是gcd(a,n)=1，如果gcd(a,n)>1,则不存在逆元：比如：18 12 #include #include using namespace std; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1,y=0; return a; } int r = exgcd(b,a%b,x,y); int t = x; x = y; y = t - a/b*y; return r; } int inv(int n,int m) { int x,y; int ans = exgcd(n,m,x,y); if(ans == 1) return (x%m+m)%m; //定义：正整数 a, n，如果有 ax ≡ 1(mod n)，则称 x 的最小整数解为 a 模 n的逆元。 else return -1; } int main() { int n,m; cin>>n>>m; int ans = inv(n,m); ans == -1 ? cout<<"没有逆元"< 三、费马小定理及欧拉定理 四、O(n)求1~n逆元表 （这个写的不是很详细，具体看那个链接）   ps: a与b对模m同余，记为a≡b(mod m) ax≡1(mod p) 读作：a关于模p的乘法逆元。