比赛 noip 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 __完全平方数 最终得分 100
用户昵称 Go灬Fire 运行时间 1.286 s
代码语言 C++ 内存使用 18.14 MiB
提交时间 2016-11-04 19:36:17
显示代码纯文本
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stdio.h>
using namespace std;
#define LL long long
#define Begin freopen("xnumber.in","r",stdin);freopen("xnumber.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
const int maxn=5005500;
const int mod=100000007;
int Prime[maxn];LL n,tot;
bool vis[maxn];
void Init();
void Get_Prime(){
	for(int i=2;i<=n+1000;i++){
		if(!vis[i])Prime[++tot]=i;
		for(int j=1;j<=tot;j++){
			if(i*Prime[j]>n)break;
			vis[i*Prime[j]]=1;
			if(i%Prime[j]==n)break;
		}
	}
}
LL Count(int date,int x){
	LL num=0;
	while(date){
		num+=date/x;
		date/=x;
	}//puts("---");
	return num;
}
LL qpow(LL x,int h){
	if(h==0)return 1;
	LL ans=1;
	while(h){
		if(h&1)ans*=x,ans%=mod;
		x*=x;x%=mod;h>>=1;
	}
	return ans;
}
int main(){
    Begin;
    Init();
    getchar();getchar();
    End;
    return 0;
}
void Init(){
	scanf("%lld",&n);
	Get_Prime();
	LL ans=1; 
	for(int i=1;Prime[i]<=n;i++){
		//printf("%d ",i);
		LL num=Count(n,Prime[i]);
		if(num%2==1)num--;
		ans*=qpow(Prime[i],num);ans%=mod; 
	}
	printf("%lld\n",ans);
}