| by XianKa | No comments

【数论】欧拉降幂,费马小定理求逆元,阶乘逆元

今天在群里看见一道题目t1

  • 首先这题模数是一个大质数,所以考虑求分母的逆元
  • 由于只需要算一次,没有变量也没有多次询问,所以直接暴力求20192019!%p的结果,然后用费马小定理求出其逆元即可
  • 对于分母,也可以用欧拉定理来降幂,由于p是个质数,所以p的欧拉函数值就是p-1,可以直接放上分子,然后对分子进行快速幂

SharedImage

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll qsm(ll n,ll k,ll md)
{
    ll res=1;
    while(k)
    {
        if(k&1) res=(res*n)%md;
        n=(n*n)%md;
        k>>=1;
    }
    return res%md;
}
int main()
{
    ll fac=1;
    for(int i=1;i<=20192019;i++) fac=(fac*i)%mod;
    ll inv=qsm(fac,mod-2,mod);
    ll son=qsm(2019,qsm(2019,2019,mod-1),mod);
    cout<<inv*son%mod<<endl;
}

 

  • 补充:
  • 对于阶乘的逆元,可以[latex]O(N)[/latex]预处理出其逆元。
  • 假设用费马小定理求出了[latex]q![/latex]的逆元[latex](q!)^{-1}[/latex]。那么就有
  • [latex](q!) * (q!)^{-1} \equiv 1[/latex]
  • [latex](q-1)! * q * (q!)^{-1} \equiv 1[/latex]
  • 从上式可以看出[latex](q-1)![/latex]的逆元就是[latex]q * q!^{-1}[/latex]
  • fact[0]=1;
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
    invfact[n]=qsm(n,mod-2);
    for(int i=n;i>=1;i--) invfact[i-1]=invfact[i]*i%mod;

     

 

发表评论