记录编号	456801	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]艾米利亚的魔法	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	9.728 s
提交时间	2017-10-05 16:48:37	内存使用	46.07 MiB

#include <cstdio>
#define maxn 1000005
typedef long long ll;
int n,G,Falsemod=54184622,fans,Truemod=27092310,A[6],M[6],minv[6],inv[6][maxn],xp[6][maxn],list[6]={0,2,3,5,7,129011};
inline int gcd(int x,int y){return !y?x:gcd(y,x%y);}
inline int qp(int x,int y,int mod)
{	ll ans=1;x%=mod;
	for(;y;y>>=1,x=(ll)x*x%mod) if(y&1) ans=(ll)ans*x%mod;
	return ans;
}
inline void init()
{	for(int i=1;i<=5;++i)
	{	xp[i][0]=1;inv[i][0]=1;
		for(int j=1;j<=G;++j) xp[i][j]=(ll)xp[i][j-1]*j%list[i];
		for(int j=1;j<=G;++j) inv[i][j]=qp(xp[i][j],list[i]-2,list[i]);
	}
	for(int i=1;i<=5;++i) M[i]=Truemod/list[i],minv[i]=qp(M[i],list[i]-2,list[i]);
}
inline int C(int x,int y,int mod,int pos){return (ll)xp[pos][x]*inv[pos][y]%mod*inv[pos][x-y]%mod;}
inline int lucas(int x,int y,int mod,int pos)
{	if(!y) return 1;
	return C(x%mod,y%mod,mod,pos)*lucas(x/mod,y/mod,mod,pos)%mod;
}
inline int CRT(int x,int y)
{	if(y>x) return 0;ll tmp=0;
	for(int i=1;i<=5;++i) A[i]=lucas(x,y,list[i],i);
	for(int i=1;i<=5;++i) tmp=(tmp+(ll)A[i]*M[i]*minv[i])%Truemod;
	return tmp;
}
int main()
{	freopen("aimiliyademagic.in","r",stdin);
	freopen("aimiliyademagic.out","w",stdout);
	scanf("%d%d",&n,&G);
	init();
	for(int i=1;i<=n;++i)
		if(gcd(i,n)==1)
			fans=((ll)fans+CRT(G,i))%Truemod;
	printf("%d",qp(n,fans+Truemod,Falsemod));
	return 0;
}