真是到很强的数学题
先利用欧拉定理A^B %p=A^(B%φ(p)+φ(p) ) %p
然后利用卢卡斯定理求出在modφ(p)的几个约数下的解
再利用中国剩余定理合并
计算答案即可
By：大奕哥
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=;
ll pri[]={,,,};
ll fac[][],inv[][],ans[],n,g;
void init(ll p,ll fac[],ll inv[])
{
fac[]=;
for(int i=;i<=p;++i)fac[i]=fac[i-]*i%p;
inv[]=inv[]=;
for(int i=;i<=p;++i)inv[i]=(p/i+)*inv[i-p%i]%p;
for(int i=;i<=p;++i)inv[i]=inv[i]*inv[i-]%p;
}
ll C(ll a,ll b,ll p,ll fac[],ll inv[])
{
if(a<b)return ;
if(a<p&&b<p)return fac[a]*inv[b]%p*inv[a-b]%p;
return C(a/p,b/p,p,fac,inv)*C(a%p,b%p,p,fac,inv)%p;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b){
x=;y=;return;
}
exgcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
}
ll CRT()
{
ll sum=;
for(int i=;i<;++i)
{
ll x,y;
exgcd((mod-)/pri[i],pri[i],x,y);
sum+=ans[i]*((mod-)/pri[i])%(mod-)*x%(mod-);
sum%=(mod-);
}
return sum;
}
void cal(ll x)
{
for(int i=;i<;++i)
{
ans[i]+=C(n,x,pri[i],fac[i],inv[i]);
ans[i]%=pri[i];
}
return;
} ll qmod(ll a,ll b)
{
ll ans=;
while(b)
{
if(b&)ans=ans*a%mod;
a=a*a%mod;b>>=;
}
return ans;
}
int main()
{
for(int i=;i<;++i)init(pri[i],fac[i],inv[i]);
scanf("%d%d",&n,&g);
for(int i=;i*i<=n;++i)
{
if(i*i==n)cal(i);
else if(n%i==)cal(i),cal(n/i);
} ll ans=CRT();
ans=qmod(g%mod,ans+mod-);
printf("%lld\n",ans);
return ;
}