洛咕 P2480 [SDOI2010]古代猪文

---

题目是要求\(G^{\sum_{d|n}C^d_n}\)。

用费马小定理\(G^{\sum_{d|n}C^d_n\text{mod 999911658}}\)

因数可以\(O(\sqrt n)\)枚举。

分解质因数，\(999911658=2×3×4679×35617\)，对这4个模数用lucas跑一遍答案，用crt合并。

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define il inline

#define vd void

#define MOD 999911659

#define Mod 999911658

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int mod[]={0,2,3,4679,35617};

int p[5][35700],inv[5][35700],ans[5];

il int pow(int x,int y,int mo){

    int ret=1;

    while(y){

        if(y&1)ret=1ll*ret*x%mo;

        x=1ll*x*x%mo;y>>=1;

    }

    return ret;

}

il int C(int x,int y,int m){return 1ll*p[m][x]*inv[m][1ll*p[m][y]*p[m][x-y]%mod[m]]%mod[m];}

il int Lucas(int x,int y,int m){

    if(x<y)return 0;if(!x)return 1;

    return 1ll*Lucas(x/mod[m],y/mod[m],m)*C(x%mod[m],y%mod[m],m)%mod[m];

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("2480.in","r",stdin);

    freopen("2480.out","w",stdout);

#endif

    int n=gi(),g=gi();

    if(g==MOD)return puts("0"),0;

    for(int i=1;i<=4;++i){

        p[i][0]=1;for(int j=1;j<mod[i];++j)p[i][j]=1ll*p[i][j-1]*j%mod[i];

        inv[i][1]=1;for(int j=2;j<mod[i];++j)inv[i][j]=(mod[i]-1ll*(mod[i]/j)*inv[i][mod[i]%j]%mod[i])%mod[i];

    }

    for(int i=1;i*i<=n;++i)

        if(n%i==0){

            for(int j=1;j<=4;++j)ans[j]=(ans[j]+Lucas(n,i,j))%mod[j];

            if(i*i!=n)for(int j=1;j<=4;++j)ans[j]=(ans[j]+Lucas(n,n/i,j))%mod[j];

        }

    int tot=0;

    for(int i=1;i<=4;++i)tot=(tot+1ll*ans[i]*(Mod/mod[i])%Mod*inv[i][(Mod/mod[i])%mod[i]]%Mod)%Mod;

    printf("%d\n",pow(g,tot,MOD));

    return 0;

}