真的可以算是一个数论比较的题目,用了几个定理揉到一起,算是数论比较综合的题目了..
首先归纳下题意：
[ans=g^{sum_{k|n}C_n^k} mod p(p=999911659)
]
嗯,大概就是个这,考虑怎么搞这个东西,先看式子第一眼,这个g的指数是个什么玩意,我们肯定是要在这个指数上搞搞啊,关于取模的和指数有关的,好像只学过欧拉定理,因为(p)是质数,所以g要么是p的倍数要么与p互质,当g是p的倍数时,则毫无疑问上式的结果是0.否则的话,我们就可以用欧拉定理对上式进行化简.
[ans=g^{sum_{k|n}C_n^k} mod p(p=99991165)=g^{sum_{k|n}C_n^kmodphi{(p)}}modp
]
接下来就主要计算指数部分了,也就是这部分(sum_{k|n}C_n^kmodphi{(p)}),(phi{(p)})=p-1,可也有(999911658)这么大,对于组合数的取模,我只学过卢卡斯定理,可卢卡斯要求p是质数啊,可(999911658)显然不是质数啊,这可咋办？
之后就是中国剩余定理登场了,中国剩余定理可以将一个数分开成几个数,再合并。
我们可以将(999911658)分解成(2 imes3 imes4679 imes35617),计算出组合数分别对他们取模的结果记为(s_1,s_2,s_3,s_4)
之后只需要求出(x≡a%s_i)(pmod{s_i}).即可,直接用朴素的crt就行...
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define RE register
#define P 999911659
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(x,y,z) for(RE int x=y;x<=z;++x)
#define fep(x,y,z) for(RE int x=y;x>=z;--x)
#define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=4e4;
ll n,g,jc[N],jc_inv[N],s[5];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
inline ll power(ll x,ll y,ll p)
{
ll ans=1;
while(y)
{
if(y&1) ans=ans*x%p;
y>>=1;
x=x*x%p;
}
return ans%p;
}
inline ll C(ll n,ll m,ll p)
{
if(n<m) return 0;
return jc[n]*jc_inv[m]%p*jc_inv[n-m]%p;
}
inline ll lucas(ll n,ll m,ll p)
{
if(!m) return 1;
return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b) {x=1;y=0;return a;}
ll d=exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-y*(a/b);
return d;
}
//2 3 4679 35617
inline ll work()
{
ll ans=0,M=P-1;
rep(i,1,4)
{
int mod;
if(i==1) mod=2;
else if(i==2) mod=3;
else if(i==3) mod=4679;
else if(i==4) mod=35617;
jc[0]=1;jc_inv[0]=1;
rep(j,1,mod) jc[j]=jc[j-1]*j%mod,jc_inv[j]=power(jc[j],mod-2,mod);
rep(j,1,sqrt(n))
if(n%j==0)
{
s[i]=(s[i]+lucas(n,j,mod))%mod;
if(j*j!=n) s[i]=(s[i]+lucas(n,n/j,mod))%mod;
}
ll Mi=M/mod;
ans=(ans+s[i]*Mi%M*power(Mi,mod-2,mod)%M)%M;
}
ans=(ans%M+M)%M;
return ans;
}
int main()
{
// freopen("1.in","r",stdin);
get(n);get(g);
if(g%P==0) {puts("0");return 0;}
putl(power(g,work(),P));
return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.