比赛 |
20160420s |
评测结果 |
AAAAAAAAAA |
题目名称 |
最小生成树 |
最终得分 |
100 |
用户昵称 |
FETS 1/3 |
运行时间 |
0.011 s |
代码语言 |
C++ |
内存使用 |
0.66 MiB |
提交时间 |
2016-04-20 09:19:06 |
显示代码纯文本
#include<cstring>
#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
#define N 30000
int vis[N];
int p[N],cnt,phi[N];
const int MOD=100000007;
int Euler(int n)
{
phi[1]=1;
for (int i=2;i<n;i++)
{
if (!vis[i])
{
p[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;j<cnt&&i*p[j]<n;++j)
{
vis[i*p[j]]=1;
if (i%p[j])
phi[i*p[j]]=phi[i]*phi[p[j]];
else
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
return cnt;
}
int main()
{
freopen("msta.in","r",stdin);
freopen("msta.out","w",stdout);
int n;
scanf("%d",&n);
Euler(N);
long long ans=1;
for(int i=1;i<=n;i++)
{
ans=1LL*ans*phi[i]%MOD;
}
printf("%d",ans);
return 0;
}