比赛 noip 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 __完全平方数 最终得分 100
用户昵称 Yniverse 运行时间 1.108 s
代码语言 C++ 内存使用 82.95 MiB
提交时间 2016-11-04 19:31:22
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 6000010
using namespace std;
typedef long long LL;
LL prime[maxn],tot,ans,Mod=100000007ll,mi[maxn],n;
bool check[maxn];
void Getprime(){
	for(int i=2;i<=n+10;i++){
		if(!check[i]) prime[++tot]=i;
		for(int j=1;j<=tot;j++){
			if(i*prime[j]>n)break;
			check[i*prime[j]]=1;
			if((i%prime[j])==0)break;
		}
	}
}
LL Siz(LL x,LL p){
	if(x<p)return 0;
	return x/p+Siz(x/p,p);
}
LL Quickpow(LL x,LL cnt){
	LL data=x,sum=1ll;
	for(;cnt;data=(data*data)%Mod,cnt>>=1ll){
		if(cnt&1) sum=(sum*data)%Mod;
	}
	return sum;
}
int main(){
	freopen("xnumber.in","r",stdin);freopen("xnumber.out","w",stdout);
	
	scanf("%lld",&n);
	Getprime();
	ans=1ll;
	for(int i=1;;){
		mi[i]+=Siz(n,prime[i]);
		if(mi[i]&1) mi[i]--;
		if(mi[i])ans=(ans*Quickpow(prime[i],mi[i]))%Mod;
		if(i<tot&&prime[i]<=n)i++;
		else break;
	}
	printf("%lld\n",ans%Mod);
	
	getchar();getchar();
	fclose(stdin);fclose(stdout);
	return 0;
}