常用逆元总结

乘法逆元在mod运算里非常重要，一下总结一些常用的逆元,假设我们有式子：

$$ans=\frac{a}{b}\mathrm{m}\mathrm{o}\mathrm{d}m$$

当m为素数p时，b的逆元为pow(b,m-2); 用快速幂计算该逆元即可 $$ans=\frac{a}{b}\mathrm{m}\mathrm{o}\mathrm{d}m=a\times pow(b,m-2)\mathrm{m}\mathrm{o}\mathrm{d}m$$

当a%b==0时，可将算式做如下边形： $$ans=\frac{a}{b}\mathrm{m}\mathrm{o}\mathrm{d}m=a\mathrm{m}\mathrm{o}\mathrm{d}(m\times b)/b$$ 上式的证明过程

特别的如果m为质数,b为阶乘数,如果打表的话前一项与后一项存在一个递推关系代码如下：

//计算组合数 #include<cstdio> typedef long long LL; const LL N=1e5+10,mod = 1e9 + 7; //计算组合数取mod(mod为质数) LL fac[N],inv[N]; LL fp(LL a,LL b) { LL ans = 1; while (b){ if (b&1)ans = ans * a % mod; a = a*a % mod; b >>= 1; } return ans; } void init() { fac[0] = inv[0] = 1; for (int i = 1;i<= N+100;i++)fac[i]=fac[i-1]*i%mod; inv[N]=fp(fac[N],mod-2); for(int i=N;i>=1;i--)inv[i-1]=inv[i]*i%mod; } int main() { init(); int n,m; while (~scanf ("%d %d",&n,&m)) printf ("%lld\n",fac[n] * inv[n-m] % mod * inv[m] % mod); } 还有一种就是用拓展欧几里得求逆元,不过当b与m不互质时(gcd(m,b)!=1),逆元不存在