比赛 noip 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 __完全平方数 最终得分 100
用户昵称 Riolu 运行时间 1.327 s
代码语言 C++ 内存使用 4.57 MiB
提交时间 2016-11-04 20:22:30
显示代码纯文本
/*=========================================*
  * Auther: Riolu
  * Time: 2016.11.4
  * ©Copyright 2016 Riolu. All Rights Reserved.
  *=========================================*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;

typedef long long ll;
const int N =5000001,M=1e8 +7;
bool pri[N];
ll n,ans=1;

ll ask(ll x){
	ll t=0,i;
	for(i=n/x;i>0;i/=x)t+=i;
	return t;
}

ll qpow(ll a,ll b){
	ll t=1,x=a%M;
	for(;b>0;b>>=1,x=(x*x)%M)
		if(b%2) t=(t*x)%M;
	return t;
}

int main(){
	freopen("xnumber.in","r",stdin);
	freopen("xnumber.out","w",stdout);

	ll i,j,sum,l;
	cin>>n;l=(n>>1)+1;
	for(i=2;i<=l;i++) if(!pri[i])
		for(j=i<<1;j<=n;j+=i)pri[j]=1;
	for(i=2;i<=l;i++) if(!pri[i]){
		j=0;
		sum=ask(i); 
		if(sum%2) sum--;
		if(sum!=0) j=qpow(i,sum);
		if(j!=0) ans=(ans*j)%M;
	}
	cout<<ans<<endl;
	return 0;
}
/*

*/