bzoj千题计划323:bzoj1951: [Sdoi2010]古代猪文(Lucas+CRT+欧拉定理)

时间:2021-11-22 20:35:25

https://www.lydsy.com/JudgeOnline/problem.php?id=1951

先欧拉降幂

然后模数质因数分解

分别计算组合数的结果,中国剩余定理合并

#include<cmath>
#include<cstdio>
#include<iostream> using namespace std; const int mod=;
const int phi=mod-; typedef long long LL; int p[];
LL mul[][]; LL c[]; void pre()
{
p[]=;
p[]=;
p[]=;
p[]=;
for(int i=;i<=;++i)
{
mul[i][]=;
for(int j=;j<=;++j) mul[i][j]=mul[i][j-]*j%p[i];
}
} LL gcd(LL a,LL b)
{
return !b ? a : gcd(b,a%b);
} LL Pow(LL a,LL b,LL mod)
{
LL ans=;
for(;b;a=a*a%mod,b>>=)
if(b&) ans=ans*a%mod;
return ans;
} LL C(LL n,LL m,int i)
{
if(m>n) return ;
return mul[i][n]*Pow(mul[i][m],p[i]-,p[i])%p[i]*Pow(mul[i][n-m],p[i]-,p[i])%p[i];
} LL Lucas(LL n,LL m,int i)
{
if(m>n) return ;
LL ans=;
for(;m;n/=p[i],m/=p[i]) ans=(ans*C(n%p[i],m%p[i],i))%p[i];
return ans;
} void exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b) x=,y=;
else exgcd(b,a%b,y,x),y-=a/b*x;
} int main()
{
pre();
LL n,g;
cin>>n>>g;
if(gcd(g,mod)!=)
{
printf("");
return ;
}
int m=sqrt(n);
for(int i=;i<=m;++i)
if(n%i==)
{
for(int j=;j<=;++j) c[j]=(c[j]+Lucas(n,i,j))%p[j];
if(n/i!=i)
for(int j=;j<=;++j) c[j]=(c[j]+Lucas(n,n/i,j))%p[j];
}
LL ans=;
LL Mi,mi,x,y;
for(int i=;i<=;++i)
{
Mi=phi/p[i];
mi=p[i];
exgcd(Mi,mi,x,y);
x=(x%mi+mi)%mi;
if(!x) x+=mi;
ans+=c[i]*Mi*x;
}
ans=Pow(g,ans,mod);
cout<<ans;
}