比赛 |
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;
- }