题意
求：
\[g^{\sum_{d|n}\binom{n}{d} } \mod 999911659 \]\(n,g \leq 10^9\)。
思路：
因为 \(999911659\) 是质数，由欧拉定理的推论，可以得到：
\[g^{\sum_{d|n}\binom{n}{d} } \mod 999911659=g^{\sum_{d|n}\binom{n}{d} \mod 999911658} \mod 999911659 \]那么现在就是要计算 \(\sum_{d|n}\binom{n}{d} \mod 999911658\)。由于 \(999911658=2 \times 3 \times 4679 \times 35617\)。那么把模数缩小，利用 Lucas 定理把 \(\binom{n}{d}\) 计算出来，分别计算出 \(sum_{d|n}\binom{n}{d}\) 对这四个质数取模的结果，记为 \(a_1,a_2,a_3,a_4\)。最后只需要求一组同余方程：
\[\begin{cases} x \equiv a_1 \pmod {2} \\ x \equiv a_2 \pmod {3} \\ x \equiv a_3 \pmod {4679} \\ x \equiv a_1 \pmod {35617} \end{cases}\]利用中国剩余定理可以得到 \(x\) 的值，那么最终的答案就是 \(g^x\)。
code：
#include<iostream>
using namespace std;
#define int long long
const int mod=999911658;
const int M=52000;
int n,jc[M],a[5],g,prime[5]={0,2,3,4679,35617},ans;
int mul(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1) res=(res*a)%p;
a=(a*a)%p;
b>>=1;
}
return res;
}
int C(int n,int m,int p)
{
if(n<m) return 0;
return jc[n]*mul(jc[m],p-2,p)%p*mul(jc[n-m],p-2,p)%p;
}
int Lucas(int n,int m,int p)
{
if(n<m) return 0;
if(!n) return 1;
return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
void CRT()
{
for(int i=1;i<=4;i++)
ans=(ans+a[i]*(mod/prime[i])%mod*mul(mod/prime[i],prime[i]-2,prime[i]))%mod;
}
void init(int p)
{
jc[0]=1;
for(int i=1;i<=p;i++)
jc[i]=(jc[i-1]*i)%p;
}
signed main()
{
scanf("%lld%lld",&n,&g);
if(g%(mod+1)==0)
{
puts("0");
return 0;
}
for(int i=1;i<=4;i++)
{
init(prime[i]);
for(int j=1;j*j<=n;j++)
{
if(n%j==0)
{
a[i]=(a[i]+Lucas(n,j,prime[i]))%prime[i];
if(j*j!=n)
{
a[i]=(a[i]+Lucas(n,n/j,prime[i]))%prime[i];
}
}
}
}
CRT();
printf("%lld\n",mul(g,ans,mod+1));
return 0;
}