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