记录编号	338277	评测结果	WWWWWWWWWWWWWWTTTTTT
题目名称	__完全平方数	最终得分	0
用户昵称	404	是否通过	未通过
代码语言	C++	运行时间	14.306 s
提交时间	2016-11-05 09:39:31	内存使用	27.06 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int mod=100000007;
int n,cnt;
ll ans=1;
int a[5005000],b[1001000],num[1005000];
ll pow(ll x,int y)
{
	ll res=1;
	for(;y;y=y>>1)
	{
		if(y&1)res=(res*x)%mod;
		x=(x*x)%mod;
	}return res;
}
void pri()
{
	memset(a,1,sizeof(a));
	for(int i=2;i<=n;i++)
	{
		if(a[i])b[++cnt]=i;
		for(int j=1;j<=cnt&&b[j]*i<=n;j++)
		{
				a[i*b[j]]=0;
				if(i%b[j]==0)break;
		}
	}
}
void pre()
{
	for(int i=2;i<=n;i++)
	{
		int x=i,j=1;
		if(a[x])continue;
		while(x>1)
		{
			if(x%b[j]==0)num[j]++,x=x/b[j];
			else j++;
		}
	}
}
int main()
{
	freopen("xnumber.in","r",stdin);
	freopen("xnumber.out","w",stdout);
	scanf("%d",&n);
	pri();pre();
	for(int i=1;i<=cnt;i++)
	  if(num[i]%2==0)ans=(ans*pow((ll)b[i],num[i]))%mod;
	  else ans=(ans*pow((ll)b[i],num[i]-1))%mod;
	printf("%I64d\n",ans);
}