记录编号	252576	评测结果	AAAAAAAAAA
题目名称	最小生成树	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-04-20 17:05:58	内存使用	0.62 MiB

#include <fstream>
#include <algorithm>
#define N 20010
using namespace std;
typedef long long ll;
ifstream in("msta.in");
ofstream out("msta.out");ll hongzhuizidongji[N]={0};ll mod=100000007;ll linkcuttree[N]={0};int n;void fuck(){int i,j;for(i=1;i<=n;i++){if(!hongzhuizidongji[i]){for(j=i;j<=n;j+=i){if(!hongzhuizidongji[j])hongzhuizidongji[j]=j;hongzhuizidongji[j]=hongzhuizidongji[j]/i;hongzhuizidongji[j]=hongzhuizidongji[j]*(i-1);}}}}void read(){in>>n;}void slayklzwii(){int i,tim,kuotashi,satoshi;for(i=1;i<=n;i++){tim+=1;satoshi=tim*kuotashi;kuotashi=satoshi*2+1;}}void work(){int i;linkcuttree[1]=1;for(i=2;i<=n;i++){linkcuttree[i]=linkcuttree[i-1]*hongzhuizidongji[i];linkcuttree[i]%=mod;}out<<linkcuttree[n]<<endl;}
int main()
{
	read();
	fuck();
	slayklzwii();
	work();
	return 0;
}