比赛 |
noip |
评测结果 |
WWWWWWWWWWWWWWTTTTTT |
题目名称 |
__完全平方数 |
最终得分 |
0 |
用户昵称 |
404 |
运行时间 |
13.431 s |
代码语言 |
C++ |
内存使用 |
21.65 MiB |
提交时间 |
2016-11-04 21:22:20 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int mod=100000007;
int n,cnt;
ll ans=1;
int a[5005000],b[1001000],num[1005000];
ll pow(ll x,int y)
{
ll res=1;
for(;y;y=y>>1)
{
if(y&1)res=(res*x)%mod;
x=(x*x)%mod;
}return res;
}
void pri()
{
memset(a,1,sizeof(a));
for(int i=2;i<=n;i++)
{
if(a[i])b[++cnt]=i;
for(int j=1;j<=cnt&&b[j]*i<=n;j++)
{
a[i*b[j]]=0;
if(i%b[j]==0)break;
}
}
}
void pre()
{
for(int i=2;i<=n;i++)
{
int x=i,j=1;
if(a[x])continue;
while(x>1)
{
if(x%b[j]==0)num[j]++,x=x/b[j];
else j++;
}
}
}
int main()
{
freopen("xnumber.in","r",stdin);
freopen("xnumber.out","w",stdout);
scanf("%d",&n);
pri();pre();
for(int i=1;i<=cnt;i++)
if(num[i]%2==0)ans=(ans*pow((ll)b[i],num[i]))%mod;
else ans=(ans*pow((ll)b[i],num[i]-1))%mod;
printf("%I64d\n",ans);
}