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

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

 

先欧拉降幂

然后模数质因数分解

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

 

#include<cmath> #include<cstdio> #include<iostream> using namespace std;const int mod=999911659; const int phi=mod-1;typedef long long LL;int p[5]; LL mul[5][35618];LL c[5];void pre() {p[1]=2;p[2]=3;p[3]=4679;p[4]=35617;for(int i=1;i<=4;++i){mul[i][0]=1;for(int j=1;j<=35617;++j) mul[i][j]=mul[i][j-1]*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=1;for(;b;a=a*a%mod,b>>=1)if(b&1) ans=ans*a%mod;return ans; }LL C(LL n,LL m,int i) {if(m>n) return 0;return mul[i][n]*Pow(mul[i][m],p[i]-2,p[i])%p[i]*Pow(mul[i][n-m],p[i]-2,p[i])%p[i]; }LL Lucas(LL n,LL m,int i) {if(m>n) return 0;LL ans=1;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=1,y=0;else exgcd(b,a%b,y,x),y-=a/b*x; }int main() {pre();LL n,g;cin>>n>>g;if(gcd(g,mod)!=1) {printf("0");return 0;}int m=sqrt(n);for(int i=1;i<=m;++i)if(n%i==0){for(int j=1;j<=4;++j) c[j]=(c[j]+Lucas(n,i,j))%p[j];if(n/i!=i) for(int j=1;j<=4;++j) c[j]=(c[j]+Lucas(n,n/i,j))%p[j]; }LL ans=0;LL Mi,mi,x,y;for(int i=1;i<=4;++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; }

 

转载于:https://www.cnblogs.com/TheRoadToTheGold/p/8993846.html

总结

以上是生活随笔为你收集整理的bzoj千题计划323：bzoj1951: [Sdoi2010]古代猪文（Lucas+CRT+欧拉定理）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。