题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1951

题目分类：数论

题意：

球G^m(mod 999911659)

m=sigma i|n {C(n,i)}

题解：

G^m(mod 999911659)=G^(m mod 999911658)(mod 999911659)

枚举约数，快速求出C（n，i）（mod 999911659）

999911658=2*3*4679*35617

可以使用中国肾盂定理求出线性同余方程组的解。

程序：

#include<cstdio>
using namespace std;
long long f[5][40000];
long long ni[5]={0,1,1,1353,-4363};
long long w[5]={0,2,3,4679,35617};
const long long mod=999911659;
inline long long exp(long long x,long long y,long long md)
{
	long long ans=1;
	while (y!=0)
	{
		if(y&1)
		{
			y--;
			ans=(ans*x)%md;
		}
		else
		{
			y/=2;
			x=x*x%md;
		}
	}return ans;
}
inline void init()
{
	for (int i=1;i<=4;i++)
	{
		f[i][0]=1;
		for (int j=1;j<=w[i];j++)
		{
			f[i][j]=(f[i][j-1]*(long long)j)%w[i];
		}
	}
}
inline long long C(long long x,long long y,long long idx)
{
	if(x<y)return 0;
	return f[idx][x]*exp((f[idx][x-y]*f[idx][y]),w[idx]-2,w[idx])%w[idx];
}
inline long long lucas(long long x,long long y,long long idx)
{
	if(y==0)return 1;
	return lucas(x/w[idx],y/w[idx],idx)*C(x%w[idx],y%w[idx],idx)%w[idx];
}
long long a[5];
inline long long CRT()
{
	long long ans=0,M=1;
	for (int i=1;i<=4;i++)M*=w[i];
	for (int i=1;i<=4;i++)
	{
	//	printf("%I64d %I64d ",ni[i],a[i]);
		ans+=(a[i]*(M/w[i])*ni[i])%M;
		ans%=M;
	}
	while (ans<=0)
	{
		ans+=M;
	}return ans;
}
int main()
{
	init();
	long long n,m;
	while (scanf("%lld %lld",&n,&m)!=EOF)
	{
		m%=mod;
		a[1]=a[2]=a[3]=a[4]=0;
		for (int i=1;i*i<=n;i++)
		{
			if(n%i==0)
			{
				for (int j=1;j<=4;j++)
				{
					a[j]+=lucas(n,i,j);a[j]%=w[j];
					if(i*i!=n)a[j]+=lucas(n,n/i,j),a[j]%=w[j];
				}
			}
		//	printf("%d %I64d %I64d %I64d %I64d\n",i,a[1],a[2],a[3],a[4]);
		}printf("%lld\n",exp(m,CRT(),mod));
	}
	return 0;
}