[BZOJ 1951] 古代猪文【Lucas定理/费马小定理/中国剩余定理/扩展

[Description] 求

[Solution] 容易得到，

所以，重点在怎么求

如果是p-1是个质数，，我们可以用sqrt(n)的时间枚举所有d,用Lucas定理分别计算求和即可。 但是我们发现p-1=2*3*4679*35617，并不是一个质数，所以Lucas定理不能用了吗？并不，我们可以算出这个合式分别对2、3、4679、35617的模值，写出四个同余方程，再用孙子定理求解即可。注意特判g==p的情况，此时费马小定理不成立，ans=0.

[Code]

#include<cmath>#include<cstdio>typedef long long ll;const int mod=999911659;ll prime[4]={2,3,4679,35617};ll num[4],inver[4];void exgcd(ll x,ll y,ll&a,ll&b){if(!y) a=1,b=0;/y); }}ll pow(ll a,ll n,int p){ll ans=1;while(n){if(n&1) ans=ans*a%p;a=a*a%p; n>>=1;}return ans;}ll C(ll m,ll n,ll p){if(m<n) return 0;if(m==n) return 1;if(n>m-n) n=m-n;ll ans=1,cm=1,cn=1;for(ll i=0;i<n;i++) cm=cm*(m-i)%p,cn=cn*(n-i)%p;return cm*pow(cn,p-2,p)%p;}ll Lucas(ll m,ll n,ll p){if(!n) return 1;return (Lucas(m/p,n/p,p)*C(m%p,n%p,p))%p;}int get(int n){for(int i=1,lim=sqrt(n)+1;i<lim;i++)if(!(n%i)){for(int j=0;j<4;j++) num[j]=(num[j]+Lucas(n,i,prime[j]))%prime[j];if(i*i-n) for(int j=0;j<4;j++) num[j]=(num[j]+Lucas(n,n/i,prime[j]))%prime[j];}ll mul=1,ans=0;for(int i=0;i<4;i++) mul*=prime[i];for(ll i=0,t;i<4;i++){exgcd(mul/prime[i],prime[i],inver[i],t);inver[i]*=mul/prime[i];}for(int i=0;i<4;i++) ans=(ans+num[i]*inver[i])%(mod-1);return (ans+(mod-1))%(mod-1);}int main(){int n,g;scanf(“%d%d”,&n,&g);if(mod==g){ printf(“0”); return 0; }g%=mod;printf(“%lld”,pow(g,get(n),mod));return 0;}

你说只有有缘人才可以取下，我看着你手中的戒指，想做你的有缘人，