比赛 |
noip |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
__完全平方数 |
最终得分 |
100 |
用户昵称 |
Lethur |
运行时间 |
3.429 s |
代码语言 |
C++ |
内存使用 |
18.75 MiB |
提交时间 |
2016-11-04 20:06:06 |
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int m=100000007;
int n,x,l;
long long ans;
int p[5000005],a[350000],b[350000];
int main()
{
freopen("xnumber.in","r",stdin);
freopen("xnumber.out","w",stdout);
ans=1;
cin>>n;
x=int(sqrt(n));
for(int i=2;i<=x;i++)
if(p[i]==0)
{
int y=n/i;
for(int j=2;j<=y;j++) p[i*j]=1;
}
for(int i=2;i<=n;i++)
if(p[i]==0)
{
l++;
a[l]=i;
}
for(int i=1;i<=l;i++)
{
x=n;
while(x/a[i]>0)
{
x=x/a[i];
b[i]=b[i]+x;
}
}
for(int i=1;i<=l;i++)
{
if(b[i]%2==1) b[i]--;
for(int j=1;j<=b[i];j++) ans=(ans*a[i])%m;
}
cout<<ans<<endl;
return 0;
}