[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;
    else{ exgcd(y,x%y,b,a); b-=a*(x/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;
}

此博客中的热门博文

图论专题总结