在做各种取余运算时，我们会发现先除和先取余的结果是不同的，这会导致计算难度的加大，乘法逆元可以解决类似的分数取余问题。
本文按照博主的学习思路排序，结论为（单个）费马小定理求乘法逆元、（单个）利用扩展欧几里得任意情况下求乘法逆元、（批量）线性递推求乘法逆元
同余的运算法则之一
定理3 ac≡bc(mod m)，且若(m,c)≡d，则a≡b(mod m/d)。——数论讲义
也就是说，同余式两边可以同除一个和模数互质的数（此时模数不变）。
费马小定理
形式1：若m是素数，则a^m≡a(mod m)。——数论讲义······①
形式2：如果m是一个素数，而整数a不是m的倍数，则有a^(m-1)≡1(mod m)。——某百科······②
由于m是一个素数，因此①到②的条件：除数a和模数m互质，等价于a不是m的倍数。
费马小定理②的推论
a^(m-1)≡1(mod m) => a*a^(m-2)≡1(mod m) => a^(m-2)≡1/a(mod m)
乘法逆元
对于正整数a和m，如果有ax≡1(mod m)，那么把这个同余方程中x的最小正整数解叫做a模m的逆元。
若a与m不互质，易证ax%m!=1，故a必与m互质
乘法逆元与费马小定理的推论
如果m是素数，有以下推论:
ax≡1(mod m) => x≡1/a(mod m) => x≡a^(m-2)(mod m)
(同余的传递性)
（单个）费马小定理求乘法逆元
计算(a/b)%m：
若m是素数：
将1/b替换成逆元x，即b^(m-2)%m。
答案为(a*b^(m-2))%m。
例题
51Nod 1013
代码
1 |
|
外层：ax+by=gcd(a,b)
内层：bx1+(a-(a/b)b)y1=gcd(a,b) 1
2
3
展开对比可得：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
### 代码
```c++
ll exgcd(ll a,ll b,ll &x,ll &y){//扩展欧几里得算法
if(b==0){//递归边界
x=1;y=0;
return a;
}
ll ret=exgcd(b,a%b,x,y);
ll tmp=y;//求解原x,y
y=x-a/b*y;
x=tmp;
return ret;//返回gcd
}
参考
扩展欧几里得算法详解
（单个）利用扩展欧几里得任意情况下求乘法逆元
计算(a/b)%m：
仍需要逆元存在，即b与m互质。
构造bx+my=gcd(b,m)=1，用exgcd求出来的x即为逆元。
代码与前面相同。
注意这里参数传m和-m都一样，答案要加m再%m。
参考
欧几里得算法心得(辗转相除法)
（批量）线性递推求乘法逆元
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
n为3e6，p>n且为质数。
洛谷P3811 【模板】乘法逆元
此时用单个求法会超时，我们可以推导递推公式。
本垃圾博主还不会用公式编辑器，于是看这里↓
线性求逆元 - Grary - 博客园
试了试，这里p也必须是质数，还不知道为什么（逃
代码
c++ #include<bits/stdc++.h> using namespace std; #define ll long long const ll MAXN=3e6+20; ll inv[MAXN]; ll n,mod; void preinv(ll num,ll p){ inv[0]=inv[1]=1; for(ll i=2;i<=num;i++){ inv[i]=(p-p/i)*inv[p%i]%p; } } int main(){ cin>>n>>mod; preinv(n,mod); for(ll i=1;i<=n;i++){ printf("%lld\n",inv[i]); } return 0; }
