逆元

意义

若有 $ax\equiv 1 \ (mod\ p)$ ，则x为a在模p下的逆元。

一个分数是不能直接模运算的，但是可以进行乘法运算 $\frac{a}{b}\%p=(a*inv(b))\%p$

实现

欧拉定理

由欧拉定理得，若gcd(a,p)=1，则 $a^{\phi (p)}\equiv 1(mod \ p)$

得到 $a*a^{\phi (p)-1}\equiv 1(mod \ p)$ ，所以 $a^{\phi (p)-1}$ ，为a在模p下的逆元。

费马小定理

对于质数p，若gcd(a,p)=1,则 $a^{p-1}\equiv 1\ (mod\ p)$

得到 $a*a^{p-2}\equiv 1\ (mod\ p)$ ， $a^{p-2}$ 是a在模p下的逆元，直接快速幂求解 $a^{p-2}$ 即可。

扩展欧几里得

由 $ax\equiv 1 \ (mod\ p)$ ，可以得到 $ax+py=1$ ，所以 $ax\equiv 1 \ (mod \ p)$ ， $py\equiv 1 \ (mod \ a)$ ，用扩欧求x,y即可。

阶乘逆元

因为 $fac[i]*inv[i]\equiv 1(mod \ p)$

所以 $fac[i+1]*inv[i+1]\equiv 1(mod \ p)$ -> $fac[i]*(i+1)*inv[i+1]\equiv 1(mod \ p)$ -> $inv[i]=(i+1)*inv[i+1]$

代码

void getinv() //fac[i]为i的阶乘
{
  fac[1]=inv[0]=1;
  for(int i=2;i<=n;++i) fac[i]=fac[i-1]*i%mod;
  inv[n]=quick_pow(fac[n],mod-2);
  for(int i=n-1;i;--i)
    inv[i]=inv[i+1]*(i+1)%mod;
}

1 - n 逆元

代码

void getinv()
{
  inv[0]=inv[1]=1;
  for(int i=2;i<=n;++i)
   inv[i]=inv[p%i]*(p-p/i)%p;
}

本博客仅为本人学习，总结，归纳，交流所用，若文章中存在错误或有不当之处，十分抱歉，劳烦指出，不胜感激！！！