洛谷P2480 [SDOI2010]古代猪文

题意：

求
$$G^{\sum\limits_{i=1}^N \! [i \mid N] \ C_N^i} \bmod \ 999911659$$

数据范围： $1 \le G \le 1000000000,1 \le N \le 1000000000$

题解：

记 $P=\sum\limits_{i=1}^N\!i\!\mid\!N \ C_N^i$
当 $(G,999911659)=1$ 时（因为 $999911659$ 为素数，不满足的情况只有 $999911659 \mid G$）
由欧拉定理
$$G^P \equiv G^{P \bmod \ \varphi(999911659)} \ (\bmod \ 999911659)$$
因为 $999911659$ 为素数，所以 $$\varphi(999911659)=999911659-1=999911658$$
接下来只需要处理 $$\sum\limits_{i=1}^N\!i\!\mid\!N \ C_N^i \ (\bmod \ 999911658)$$ 即可
注意到 $999911658$ 不是素数，但对 $N$ 的每一个因数计算 $C_N^i$ 时都使用一次扩展卢卡斯定理会超时，考虑先行分解素因子
$$999911658=2×3×4679×35617$$
对每个素因子使用卢卡斯定理后再用中国剩余定理合并答案即可
注意，欧拉定理使用条件为 $(a,m)=1$ ，不满足时需要特判

代码：

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int mod=999911658;
int n,g;
int fac[50010],a[5],p[5]={0,2,3,4679,35617};
inline int Pow(int a,int b,int p){
    int res=1;
    for(;b;b>>=1){
        if(b&1)
            (res*=a)%=p;
        (a*=a)%=p;
    }
    return res;
}
inline void init(int p){
    fac[0]=1;
    for(int i=1;i<=p;i++)
        fac[i]=fac[i-1]*i%p;
}
inline int C(int n,int m,int p){
    if(n<m)
        return 0;
    return fac[n]*Pow(fac[m],p-2,p)%p*Pow(fac[n-m],p-2,p)%p;
}
int Lucas(int n,int m,int p){
    if(n==0) 
        return 1;
    if(n<m) 
        return 0;
    if(n==0) return 1;
    return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
inline int crt(){
    int res=0;
    for(int i=1;i<=4;i++)
        res=(res+a[i]*(mod/p[i])%mod*Pow(mod/p[i],p[i]-2,p[i]))%mod;
    return res;
}
signed main(){
    scanf("%lld%lld",&n,&g);
    if(g%(mod+1)==0){
        puts("0");
        return 0;
    }
    for(int k=1;k<=4;k++){
        init(p[k]);
        for(int i=1;i*i<=n;i++)
            if(n%i==0){
                a[k]=(a[k]+Lucas(n,i,p[k]))%p[k];
                if(i*i!=n)
                    a[k]=(a[k]+Lucas(n,n/i,p[k]))%p[k];
            }
    }
    printf("%lld\n",Pow(g,crt(),mod+1));
    return 0;
}