好吧刚开始以为扩展卢卡斯然后就往上套。。结果奇奇怪怪又WA又T。。。后来才意识到它的因子都是质数。。。qwq怕不是这就是学知识学傻了。。
题意：$ G^{\Sigma_{d|n} \space C_n^d}\space mod \space 999911659$
首先发现999911659是个质数，所以根据欧拉定理的推论有
$ G^{\Sigma_{d|n}\space C_n^d} \equiv G^{\Sigma_{d|n}\space C_n^d\space mod \space\phi(999911659)} \space mod \space 999911659$ ，而$\phi(999911659)=999911658$
对$999911658$算数基本定理分解$999911658= 2*3*4679*35617$,
所以我们用卢卡斯可以求出$ \Sigma_{d|n}\space C_n^d\space mod \space p_i$,再把他们中国剩余定理合并就好了；
#include<cstdio>
#include<iostream>
#define ll long long
#define R register ll
using namespace std;
const int mod[]={,,,},md=,mmd=;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int fac[];
inline ll qpow(ll a,ll b,ll p) { R ret=; a%=p;
for(;b;b>>=,(a*=a)%=p) if(b&) (ret*=a)%=p; return ret;
}
inline void exgcd(ll a,ll b,ll& x,ll& y) {
if(!b) {x=,y=; return ;}
exgcd(b,a%b,y,x),y-=a/b*x;
}
inline ll Inv(ll n,ll p) {
R x,y; exgcd(n,p,x,y); return (x%p+p)%p;
}
inline ll C(ll n,ll m,ll p) {
if(n<m) return ; return fac[n]*Inv(fac[n-m],p)%p*Inv(fac[m],p)%p;
}
inline ll L(ll n,ll m,ll p) {
if(n<m) return ; if(!n) return ;
return L(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
ll n,G,anss,ans[];
signed main() { fac[]=;
n=g(),G=g(); G%=md+; if(!G) {printf("0\n"); return ;}
for(R i=;i<mod[];++i) fac[i]=(ll)fac[i-]*i%md;
for(R i=;i*i<=n;++i) if(n%i==) {
for(R j=;j<=;++j) ans[j]=(ans[j]+L(n,i,mod[j]))%mod[j];
if(i*i!=n) for(R j=;j<=;++j) ans[j]=(ans[j]+L(n,n/i,mod[j]))%mod[j];
} for(R i=;i<=;++i) anss+=ans[i]*Inv(md/mod[i],mod[i])%md*md/mod[i]%md;
printf("%lld\n",qpow(G,anss,mmd));
}
2019.05.18