BZOJ1951-[Sdoi2010]古代猪文

BZOJ1951-[Sdoi2010]古代猪文

　　题意：

　　题解：

　　　　显然，这题是求$g^{Sigma_{i|n}C_{n}^{i}} pmod {999911659}$。由于p（p指模数999911659）是质数，由费马小定理得，指数只要对p-1取模就好了。

　　　　然而p-1不是质数，这是一件很尴尬的事，但是我们发现$999911659-1=2*3*4679*35617$，而且这四个数都是质数。所以我们只要求出$C_{n}^{i}$对这四个数取模的值，然后就可以用中国剩余定理求出对p-1取模的值了。

　　　　因为n非常大，所以求$C_{n}^{i}$对这四个数取模的值，我们要用lucas定理求。

　　　　然而这题有个非常坑的地方，就是如果$g=999911659$要输出0。这里需要特判一下。

#include<cstdio>
typedef long long ll;
const int P=999911659,maxn=5,maxm=100000;
ll fpow(ll a,ll b,ll p){
    ll ans=1;
    for(;b;b>>=1,a=a*a%p) if(b&1) ans=ans*a%p;
    return ans;
}
int n,g,p; ll ans=0;int mod[maxn+10]={0,2,3,4679,35617},a[maxm+10][maxn+10],v[maxm+10],cnt;
ll fac[maxm+10],invfac[maxm+10];
void prework(){
    fac[0]=invfac[0]=1;
    for(int i=1;i<=p;++i){
        fac[i]=fac[i-1]*i%p;
        invfac[i]=fpow(fac[i],p-2,p);
    }
}
ll C(int a,int b){
    if(a>b) return 0;
    return fac[b]*invfac[a]%p*invfac[b-a]%p;
}
ll lucas(int a,int b){
    ll ans=1;
    for(;a;a/=p,b/=p) ans=ans*C(a%p,b%p)%p;
    return ans;
}
int main(){
    scanf("%d%d",&n,&g);
    if(g==P){
        printf("0"); return 0;
    }
    for(int i=1;i*i<=n;++i) if(n%i==0){
        v[++cnt]=i; if(i!=n/i) v[++cnt]=n/i;
    }
    for(int i=1;i<=4;++i){
        p=mod[i]; prework();
        for(int j=1;j<=cnt;++j) a[j][i]=lucas(v[j],n);
    }
    for(int i=1;i<=cnt;++i){
        ll now=0;
        for(int j=1;j<=4;++j){
            int val=(P-1)/mod[j];
            (now+=1ll*a[i][j]*val%(P-1)*fpow(val,mod[j]-2,mod[j]))%=(P-1);
        }
        ans=(ans+now)%(P-1);
    }
    printf("%lld",fpow(g,ans,P)); return 0;
}