什么是逆元？
如果 \(ax\equiv 1(\mod p)\)，且 \(a\) 与 \(p\) 互质 \(\gcd(a,p)=1\)，则 \(x\) 是 \(a\) 在模 \(p\) 意义上的逆元，也就是 \(a\equiv x^{-1} (\mod p)\)。
\(\mathcal{first}\).费马小定理求逆元
我们知道费马小定理是：\(a^{p-1}\equiv 1(\mod p)\)。
两边同时乘上 \(a^{-1}\)，就转换成 \(a^{p-2}\equiv a^{-1}(\mod p)\)。用一个快速幂即可得到 \(a\) 的逆元。
int pow(int a, int b, int p){
int ret=1;
while(b){
if(b&1)
ret=(ret*a)%p;
a=(a*a)%p;
b>>=1;
}
return ret;
}
int inv(int a, int p){
return pow(a,p-2,p);
}
\(\mathcal{second}\).拓展欧几里得求逆元
我们知道，拓展欧几里得是用来求解 \(ax+py=\gcd(a,p)\)，又因为 \(p\) 是质数，即 \(ax\equiv 1(\mod p)\)。所以方程的 \(x\) 就是 \(a\)的逆元。
void exgcd(int a,int b){
if(!b){x=1,y=0;return ;}
exgcd(b,a%b);
int t=x;
x=y,y=t-a/b*y;
}
int main(){
int n,p;
scanf("%d%d",&n,&p);
exgcd(i,p);
cout<<(x%p+p)%x;
return 0;
}
third.线性推逆元
首先我们设，\(k=\lfloor{\frac{p}{i}}\rfloor,r=p\mod i\)，那么就能知道 \(k\times i+r\equiv 0(\mod p)\)。
然后我们将等式两边同时乘上 $i^{-1} r^{-1} $，就能得到 \(k\times r^{-1}+i^{-1}\equiv 0(\mod p)\)。
把 \(k\times r^{-1}\) 移到右边去，即 \(i^{-1} \equiv -k\times r^{-1}(\mod p)\)。
也就是 \(i^{-1}\equiv -\lfloor{\frac{p}{i}}\rfloor\times(p\mod i)^{-1} (\mod i)\)。
inv[1]=1;
for(int i=2;i<p;++i)
inv[i]=(p-p/i)*inv[p%i]%p;