记录编号	338289	评测结果	AAAAAAAAAAAAAAAAAAAT
题目名称	__完全平方数	最终得分	95
用户昵称	goodqt	是否通过	未通过
代码语言	C++	运行时间	5.489 s
提交时间	2016-11-05 09:46:07	内存使用	62.28 MiB

#include <cstdio>

int n;
int prime_count;
int prime[5000050];
bool not_prime[5000050];
int last[5000050];
int prime_total[5000050];

int main(void)
{
	long long answer = 1;
	int i,j;
	
	freopen("xnumber.in","r",stdin);
	freopen("xnumber.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i = 2;i <= n;++i)
	{
		if(!not_prime[i]){
			prime[prime_count++] = i;
			last[i] = prime_count - 1;
		}
		for(j = 0;j < prime_count && 1ll * i * prime[j] <= n;++j)
		{
			not_prime[i * prime[j]] = true;
			last[i * prime[j]] = j;
			if((i % prime[j]) == 0)
				break;
		}
	}
	
	for(i = 2;i <= n;++i)
	{
		j = i;
		while(j > 1)
		{
			++prime_total[last[j]];
			if(0 == (prime_total[last[j]] & 1))
				answer = (1ll * prime[last[j]] * prime[last[j]]) % 100000007 * answer % 100000007;
			j /= prime[last[j]];
		}
	}
	
	printf("%d\n",answer);
	
	return 0;
}