形式化题意
给定 \(n,g\) 和模数 \(P=999911659\)（一个质数），求以下柿子的值。
\[g^{\sum_{i|n}C_n^i} \bmod P
\]
知识点
扩展欧拉定理、Lucas 定理、中国剩余定理 CRT、exLucas 算法。
基础数论全家桶。
解法
发现指数会非常大，先用扩展欧拉定理缩小指数，得：
\[g^{\sum_{i|n}C_n^i} \equiv g^{\left(\sum_{i|n}C_n^i\right) \bmod (P-1)} \pmod P
\]
现在考虑计算这个柿子：
\[\left(\sum_{i|n}C_n^i\right) \bmod (P-1)
\]
于是 \(\mathcal{\Theta}(\sqrt n)\) 枚举 \(i\)，求出每个 \(C_n^i \bmod (P-1)\) 即可。
一个问题是，模数 \(P-1\) 不是质数，因此用不了 Lucas 定理。但是发现 \(P-1=2\cdot3\cdot4679\cdot35617\)，恰好是四个质数之积。于是可以分别用 Lucas 定理求出 \(C_n^i\) 对 \(2,3,4679,35617\) 取模的结果，然后 CRT 合并即可。这被称为 exLucas 算法。
注意特判 \(g=P\)。
Code
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define per(i,a,b) for(int i(a);i>b;--i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define pert(i,a,b) for(int i(a);i>=b;--i)
#define int long long
using namespace std;
constexpr int P=999911659,N=4e4;
constexpr int FAC[4]={2,3,4679,35617};
constexpr int COEF[4]={499955829,333303886,289138806,877424796};
// P-1=2*3*4679*35617
// COEF为CRT的系数，预先计算好
int fac[4][N],inv[4][N];
int ksm(int x,int y,int m){int res=1;while(y){if(y&1) (res*=x)%=m;(x*=x)%=m,y>>=1;}return res;
}
int c(int m,int n,int k){if(m<0||n<0||m<n) return 0;return fac[k][m]*inv[k][n]%FAC[k]*inv[k][m-n]%FAC[k];
}
int lucas(int m,int n,int k){if(!m||!n) return 1;return lucas(m/FAC[k],n/FAC[k],k)*c(m%FAC[k],n%FAC[k],k)%FAC[k];
}
int comb(int m,int n){ // 计算组合数C(m,n) mod (P-1)int res=0;rep(i,0,4){(res+=lucas(m,n,i)*COEF[i])%=P-1;}return res%(P-1);
}
signed main(){int n,g,sum=0;cin>>n>>g;rep(k,0,4){fac[k][0]=inv[k][0]=1;rep(i,1,FAC[k]) fac[k][i]=fac[k][i-1]*i%FAC[k];inv[k][FAC[k]-1]=ksm(fac[k][FAC[k]-1],FAC[k]-2,FAC[k]);pert(i,FAC[k]-2,1) inv[k][i]=inv[k][i+1]*(i+1)%FAC[k];}if(g%P==0){ // 特判cout<<0;return 0;}for(int i=1;i*i<=n;++i){if(n%i==0){(sum+=comb(n,i))%=P-1;if(i*i<n) (sum+=comb(n,n/i))%=P-1;}}cout<<(ksm(g,sum,P)+P)%P<<endl;return 0;
}