题目
提交记录
除了特判全RE

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=50010,p=999911659,M=999911658;
ll a[N],b[N]={0,2,3,4679,35617},c[N];
ll x,y;
ll init(ll mod)
{
	c[0]=1;	 
    for(ll i=1;i<=mod;i++)
		c[i]=(c[i-1]*i)%mod;
}
ll ksm(ll a1,ll b1,ll m)		//快速幂 
{
	ll base=a1,ans=1;
	while(b1)
	{
		if(b1&1) ans=ans*base%m;
		b1>>=1; 
		base=base*base%m;
	}
	return ans%m;
} 
ll C(ll n,ll m,ll mod)		//组合数 
{
	if(n<m) return 0;
    return c[n]*ksm(c[m],mod-2,mod)%mod*ksm(c[n-m],mod-2,mod)%mod; 	//费马小定理求乘法逆元 
}
ll Lucas(ll n,ll m,ll mod)		//Lucas定理 
{
	if(n<m) return 0;
    if(n==0||m==0) return 1;
    return Lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod;
}
void exgcd(ll a1,ll b1)	//扩欧 
{
	if(b1==0)
	{
		x=1,y=0;
		return;
	}
	exgcd(b1,a1%b1);
	ll z=x;
	x=y;
	y=z-y*(a1/b1);
}
ll crt()	//中国剩余定理 
{
	ll ans=0,Mi,d;
	for(int i=1;i<=4;i++)
	{
		Mi=M/b[i];
		exgcd(Mi,b[i]);
		ans=((ans+Mi*x*a[i])%M+M)%M;
	}
	return (ans+M)%M;
}
int main()
{
	ll n,g;
	cin>>n>>g;
	if(g%p==0)
	{
		cout<<0;
		return 0;
	}
	for(ll i=1;i<=4;i++)
	{
		init(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];
			}
		}		
	}
	ll sum=crt();
	cout<<ksm(g,sum,p);
	return 0;
}