乘法逆元费马小定理

2018-09-25 21:12:46


//inv[i]=i^(mod-2)
//逆元的含义:模mod意义下,1个数a如果有逆元x,那么除以a相当于乘以x。
#define ll long long
ll inv[50010],fac[50010];
int mod=1e9+7;

ll pow(int a,int b,int mod)
{
    ll ans=0,base=a;
    while(b)
    {
        if(b&1)ans=base*a;
        b>>=1;
        base*=base;
    }
    return ans;
}
//计算组合数时需要用到阶乘的逆元,也可以做到O(n)递推
//inv[i]=inv[i+1]*(i+1)%mod
for(int i=1;i<=n;i++)fac[i]=i*fac[i-1]%mod;
inv[n]=pow(fac[n],mod-2,mod);
for(int i=n-1;i;i--)
inv[i]=(inv[i+1]*(i+1))%mod;