定义
这里x就是a的逆元。
一个数有逆元的充分必要条件是gcd(a,p)=1，此时逆元唯一存在。
求解逆元的方式
拓展欧几里
若m不为质数，可以使用拓展欧几里得求逆元
根据裴蜀定理，若gcd(a,b)=1则gcd是a,b两个数线性组合的最小值，其他组合都是gcd的倍数。
gcd(a,b)=1，满足
移项得
即ax≡1 mod ，此时的x就是逆元。实际上线性不定方程组有无穷多解，这里只求正的最小逆元。
推导过程
扩欧代码
代码语言：javascript复制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,x,y);
int z=x;x=y;y=z-y*(a/b);
return d;
}
ans=(x%b b)%b;//x可能是负数，需要处理费马小定理
若模数p为质数，还可以根据费马小定理求逆元
，此时逆元x可取为
。
线性求逆元
模数p为质数，可在线性时间推出1∼n的所有逆元。
证明
由上可得出 dp[i]=(p-p/i)*dp[p%i]
常见用途
将对结果取余的较大数字的除法，转成乘法进行计算。
Q.E.D.
