对于正整数和，如果有， 那么把这个同余方程中的最小正整数解叫做模的逆元。

个人理解：

在一些题目中，经常因为数据过大，题目要求结果要模除一个数，常见的mod=1e9+7 （素数）

有时候，代码运算过程中会用到除法，而所有数据都已经模除了mod，导致除法可能会失真。

比如在mod=14的情况下，我要求25/5的值（理应是5），但是这里的25早已经不是25，

而是25%mod=11,

这时候得到的值其实是11/5=2，已经不是正确值5了。

这种时候乘法逆元就横空出世了。。

先声明，我要求的 a/b 是在整数范围内进行的，也就是b能整除a，乘法逆元才适用

意义： 上面的例子中，a=25，b=5.a/b=5。而mod=14，a在模除了mod之后再计算a/b的结果是错的。
有逆元的前提是，b和mod是互质的。
想得到正确结果，假设b关于mod的逆元为inv。
那么： a/b = (a*inv)%mod;（公式，不做证明了）
也就是把a除以一个数，化作了a乘以一个数。 b和inv的关系是 (b*inv)%mod=1;是不是有点像倒数

求b关于mod的逆元。 由于b与mod互质，即最大公约数为1。那么对于 b*x + mod*y = 1 存在一个最小的正整数x，这个x就是b关于mod的逆元
拓展欧几里得个人总结：点击打开链接
求b关于mod的逆元： #include int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1;y=0; return a; } int d=exgcd(b,a%b,y,x); y=y-a/b*x; return d; } int inv(int b,int mod)//求b关于mod的逆元 { int x,y; exgcd(b,mod,x,y); return (x%mod+mod)%mod; } int main() { int b, mod=14; while(~scanf("%d",&b)) { printf("b关于mod的逆元:%d ",inv(b,mod)); } return 0; }

在mod是素数的情况下，对任意整数 b 都有bp≡b(mod)p


即 如果b无法被mod整除，则有 （b的（mod-1）次幂）%mod=1 （b * b的mod-2次幂）%mod=1； 所以b的mod-2次幂%mod，就是b关于mod的逆元

上面这串话，我理解不了。 反正公式就是： b关于mod的逆元 inv = （b的mod-2次幂）%mod；
求b关于mod的逆元（mod必须是素数才可以） #include int qpow(int x,int m,int mod)//快速幂，求x的m次方 { int ans=1; while(m) { if(m%2) ans=(ans*x)%mod; x=(x*x)%mod; m=m/2; } return ans; } int inv(int b,int mod)//求b关于mod的逆元 { return qpow(b,mod-2,mod); } int main() { int b, mod=17; while(~scanf("%d",&b)) { printf("b关于mod的逆元:%d ",inv(b,mod)); } return 0; }

#include const int mod=17; int inv(int b,int mod) { if(b==1)return 1; return (mod-mod/b)*inv(mod%b,mod)%mod; } int main() { for(int i=1;i