首页 > 代码库 > 最小生成树

最小生成树

Description

话说正在 jmy 愁苦如何筹钱给大家买汽水的时候,他遇上了一位魔法师。魔法师希望 jmy能帮他破解魔法书的咒语。如果 jmy 做到了,就帮他付所有买汽水的钱。
魔法书上画了一个完全图(每两个点之间有且只有一条边),每个点都有一个独一无二的[1,n]内的编号,jmy 的任务是要找到最小生成树,以此作为魔法树,从而破解咒语。
对于完全图的边(i,j) (i≠j)的边权恰好就等于 i,j 两个数字的最大公约数。
特别地,要作为魔法树,必须满足树指定某个点为根后,所有除根以外的节点的父亲的标号必须小于自身标号。
jmy 一眼就看出了最小生成树的边权和。然而咒语却是最小生成树的个数。 为了保证大家都有汽水喝,你能帮帮 jmy 吗?

Input

一行仅一个数 N,表示完全图的大小。

Output

一行一个整数,表示答案对 100,000,007 取模(mod)的结果。

Sample Input

3

Sample Output

2

Hint

【数据规模】
对于 10%的数据,N≤5;
对于 30%的数据,N≤8;
对于 40%的数据,N≤10;
对于 70%的数据,N≤5,000;
对于 100%的数据,N≤20,000。

Source

数学,欧拉函数

 

首先必须要得出是最小生成树的权值和一定是n-1,(每个点都与1连),所以相连的必须是互质的,这就是欧拉函数,每个点与小于自己的与自己互质的数连起来,(特别的φ(1)=1),所以相当于是乘法原理,得到欧拉函数后相乘到n就是ans.
 1 #include<algorithm>
 2 #include<iostream>
 3 #include<iomanip>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cstdio>
 7 #include<queue>
 8 #include<ctime>
 9 #include<cmath>
10 #include<stack>
11 #include<map>
12 #include<set>
13 #define rep(i,a,b) for(register int i=a;i<=b;i++)
14 #define il inline
15 #define ll long long
16 using namespace std;
17 const int N=20010;
18 ll prime[N],phi[N];
19 bool is[N];
20 int n;
21 void Eular() {
22   memset(is,1,sizeof(is));
23   is[1]=0;int cnt=0;
24   phi[1]=1;
25   rep(i,2,n) {
26     if(is[i]) prime[++cnt]=i,phi[i]=i-1;
27     for(int j=1;j<=cnt&&prime[j]*i<=n;j++) {
28       is[prime[j]*i]=false;
29       if(i%prime[j]==0) phi[i*prime[j]]=prime[j]*phi[i];
30       else phi[i*prime[j]]=(prime[j]-1) * phi[i];
31     }
32   }
33 }
34 ll gl();
35 ll mod=100000007;
36 int main() {
37     freopen("gcdsum.in","r",stdin);
38     freopen("gcdsum.out","w",stdout);
39     scanf("%d",&n);
40     Eular();
41     ll ans=1;
42     rep(i,1,n) ans=(ans*phi[i])%mod;
43     cout<<ans;
44     return 0;
45 }
46 ll gl() {
47     ll res=0,f=1;
48     char ch=getchar();
49     while((ch<0||ch>9)&&ch!=-) ch=getchar();
50     if(ch==-) ch=getchar(),f=-1;
51     while(ch>=0&&ch<=9) res=res*10+ch-0,ch=getchar();
52     return res*f;
53 }

  

最小生成树