[MST]JZOJ 5888 GCD生成树

Description

 

Input

Output

 

Sample Input

5
5 6 7 10 21

Sample Output

17

 

Data Constraint

 

Hint

分析

随便搞一个最大生成树就好了

并查集优化，用个Rev数组记录编号

 

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+10;
int rev[N],a[N],f[N];
int n,mxn;
long long ans;

int Get_F(int x) {return x==f[x]?x:f[x]=Get_F(f[x]);}

int main() {
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d",&a[i]);mxn=max(mxn,a[i]);
        if (!rev[a[i]]) f[i]=rev[a[i]]=i; else ans+=a[i];
    }
    for (int i=mxn;i;i--) {
        int x=0;
        for (int j=1;i*j<=mxn;j++)
        if (rev[i*j]) {
            int y=Get_F(rev[i*j]);
            if (!x) x=y;
            else {
                if (x==y) continue;
                ans+=i;f[y]=x;
            }
        }
    }
    printf("%lld",ans);
}