记录编号	336386	评测结果	AAAAAAAAAA
题目名称	最小生成树	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-11-03 08:18:42	内存使用	0.49 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 20005, mod = 100000007;
bool isnotprime[maxn]={1,1};
int prime[maxn], P;
int phi[maxn];
ll preprocess(int n) {
	phi[1] = 1;
	for(int i=2; i<=n; ++i) {
		if(!isnotprime[i]) {
			prime[++P] = i;
			phi[i] = i-1;
		}
		for(int j=1; j<=P && i*prime[j]<=n; ++j) {
			isnotprime[i*prime[j]] = 1;
			if(i%prime[j]==0) {
				phi[i*prime[j]] = phi[i]*prime[j];
				break;
			} else 
				phi[i*prime[j]] = phi[i]*(prime[j]-1);
		}
	}
	ll ans = 1;
	for(int i=2; i<=n; ++i) ans *= phi[i], ans %= mod;
	return ans;
}

int main() {
	freopen("msta.in","r",stdin);
	freopen("msta.out","w",stdout);
	int N; 
	scanf("%d", &N);
	printf("%lld\n", preprocess(N));
	getchar(), getchar();
	return 0;
}