什么是逆元？

如果 \(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;