题目描述：
猪王国的文明源远流长，博大精深。
iPig在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为N。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。
iPig打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的k分之一，其中k是N的一个正约数（可以是1和N）。不过具体是哪k分之一，以及k是多少，由于历史过于久远，已经无从考证了。
iPig觉得只要符合文献，每一种能整除N的k都是有可能的。他打算考虑到所有可能的k。显然当k等于某个定值时，该朝的猪文文字个数为N / k。然而从N个文字中保留下N / k个的情况也是相当多的。iPig预计，如果所有可能的k的所有情况数加起来为P的话，那么他研究古代文字的代价将会是G的P次方。
现在他想知道猪王国研究古代文字的代价是多少。由于iPig觉得这个数字可能是天文数字，所以你只需要告诉他答案除以999911659的余数就可以了。
题解：
其实就是数论的合集。
要用到费马小定理，快速幂，Lucas定理，中国剩余定理。
这里推荐一篇中国剩余定理的讲解：
https://www.cnblogs.com/yangsongyi/p/9867057.html
以及本题的：
https://www.cnblogs.com/342zhuyongqi/p/9855709.html
最后不要忘了特判！！！
最后附上代码：
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int mod=999911658; typedef long long ll; ll n,g,b[5]={0,2,3,4679,35617},f[50010],a[5],val; ll mul(ll x,ll y,ll p) { ll ans=0; while(y) { if(y&1) ans=(ans+x)%p; x=(x+x)%p; y>>=1; } return ans; } ll pow(ll x,ll y,ll p) { ll ans=1; while(y) { if(y&1) ans=mul(ans,x,p); x=mul(x,x,p); y>>=1; } return ans; } void work(ll p) { f[0]=1; for(ll i=1;i<=p;i++) f[i]=mul(f[i-1],i,p); } ll C(ll x,ll y,ll p) { if(x<y) return 0; return mul(f[x],mul(pow(f[y],p-2,p),pow(f[x-y],p-2,p),p),p); } ll lucas(ll x,ll y,ll p) { if(x<y) return 0; if(x==0) return 1; return mul(lucas(x/p,y/p,p),C(x%p,y%p,p),p); } ll exgcd(ll ai,ll bi,ll &x,ll &y) { if(bi==0) { x=1; y=0; return ai; } ll cnt=exgcd(bi,ai%bi,x,y); ll idx=x; x=y; y=idx-ai/bi*y; return cnt; } ll excrt() { ll x=0,y=0; ll M=b[1],ans=a[1]; for(int i=2;i<=4;i++) { ll ai=M,bi=b[i],c=((a[i]-ans)%bi+bi)%bi; ll gcd=exgcd(ai,bi,x,y),idx=bi/gcd; if(c%gcd!=0) return -1; x=mul(x,c/gcd,idx); ans+=x*M; M*=idx; ans=(ans%M+M)%M; } return (ans%M+M)%M; } int main() { scanf("%lld%lld",&n,&g); if(g%(mod+1)==0)//特判很重要！！！ { printf("0"); return 0; } for(int i=1;i<=4;i++) { work(b[i]); for(ll j=1;j*j<=n;j++) { if(n%j==0) { a[i]=(a[i]+lucas(n,j,b[i]))%b[i]; if(j*j!=n) a[i]=(a[i]+lucas(n,n/j,b[i]))%b[i]; } } } val=excrt(); printf("%lld",pow(g,val,mod+1)); }