10.02T5 枚举因数+纵向思考

Description

Input

　　输入文件为二行，第一行为N,第二行为N个数Ai。

Output

一个数即答案

Sample Input

5 5 6 7 10 21

Sample Output

Hint

【数据规模与约定】

题解：

首先最暴力的做法肯定就是枚举n^2条边然后进行排序，接着我们再用kruskal求一遍最大生成树就可以了

然后我们看部分数据怎么处理，首先我们知道如果ai是有重复的话实际上就是一样的，首先可以去重在剩下的数字里面进行暴力

接下来我们考虑一个问题，如果一条边的权值是 i 那么它一定是由k1*i,k2*i 的点之间的。

显然按照题目的数据范围我们可以暴力统计每一个数字的所有因数，然后考虑在尽量大的相同的因子的两个数之间连边

所以这里我们可以使用vector进行统计，vector i 存储的是因数有 i 的全部数字的编号，然后跑kruskal的时候我们可以从大到小枚举这个 i 的编号连边，用并查集维护一下，输出答案就可以了

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 using namespace std;
 5 vector<int>fac[100000];
 6 int max0,fa[100005],n,a[100005];
 7 int read(){
 8     int f=1,x=0;
 9     char c=getchar();
10     while(!isdigit(c)){
11         if(c=='-')f=-1;
12         c=getchar();
13     }
14     while(isdigit(c)){
15         x=(x<<3)+(x<<1)+c-'0';
16         c=getchar();
17     }
18     return x*f;
19 }
20 
21 int find(int x){
22     if(x!=fa[x])return fa[x]=find(fa[x]);
23     return fa[x];
24 }
25 void merge(int x,int y){
26     int f1=find(x),f2=find(y);
27     if(f1!=f2){
28         fa[f1]=f2;
29     }
30 }
31 void kruskal(){
32     long long ans=0;
33     int cnt=0;
34     for(int i=max0;i>=1;i--){
35         for(int j=1;j<fac[i].size();j++){
36             int x=fac[i][j],y=fac[i][j-1];
37             if(find(x)!=find(y)){
38                 merge(x,y);
39                 ans+=i;
40                 if(cnt==n-1){
41                     cout<<ans;
42                     exit(0);
43                 }    
44             }
45         }
46     }
47     cout<<ans;
48 }
49 int main(){
50     n=read();
51     for(int i=1;i<=n;i++){
52         a[i]=read();
53         fa[i]=i;
54         max0=max(max0,a[i]);
55     }
56     for(int i=1;i<=n;i++){
57         for(int j=1;j*j<=a[i];j++){//暴力分解每一个数字的因子 
58             if(a[i]%j==0){//如果可以整除就代表可以组成gcd 
59                 fac[j].push_back(i);//那么这个数字的倍数里面就会有这个数字 
60                 fac[a[i]/j].push_back(i);//同样这个数字因子被除了之后的里面也会有这个数字 
61             }
62         }
63     }
64     kruskal();
65 }

over