Proficient.
Put your skills to the test.

Problem summary

Every array element is a vertex of a complete graph; edge(i,j) has weight gcd(a[i],a[j]). Find the weight of a maximum spanning tree without explicitly constructing all quadratic many edges.

Constraints

1≤n≤1000000;1≤a[i]≤1000000.

Worked example

Original statement sample.

10
3 12 4 6 13 18 12 8 7 11

38

Solution analysis

1. Equal-valued vertices can be joined immediately: f copies of value v contribute(f−1)v and leave one representative. Such edges have the largest possible weight incident to a copy, so they are safe maximum-spanning-tree choices.
2. Process candidate divisors d from the maximum value down to1. Enumerate all present multiples of d and join their DSU components through one anchor. Every successful union adds d. Although the actual gcd of a chosen pair might appear larger, pairs with a larger common divisor have already been connected at an earlier stage.
3. For values[6,10,15], divisor5 joins10 and15 for weight5. Divisor3 joins6 to their component for weight3. The result8 is optimal; processing divisor2 later cannot add a cycle. In the displayed sample, the duplicate12 first contributes12 and the remaining unions produce total38.

Why it works

At threshold d, all vertices whose values share any divisor at least d are connected exactly as in descending Kruskal. Within one divisor clique, a star connects the same components as all clique edges. A union first becoming possible at d cannot have a larger actual gcd, since that larger divisor was already processed. Thus the implicit process performs safe maximum-weight Kruskal unions.

Watch out. Use long long for the total: it can approach10^12. Keep duplicate contributions; compressing values without them loses vertices. A one-vertex graph has answer0.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    const int limit=1000000;
    vector<int>frequency(limit+1);
    int maximum=0;
    for(int i=0;i<n;i++){
        int value;
        cin>>value;
        frequency[value]++;
        maximum=max(maximum,value);
    }
    vector<int>parent(maximum+1),size(maximum+1,1);
    iota(parent.begin(),parent.end(),0);
    auto find=[&](int vertex){
        while(vertex!=parent[vertex]){
            parent[vertex]=parent[parent[vertex]];
            vertex=parent[vertex];
        }
        return vertex;
    };
    long long answer=0;
    for(int value=1;value<=maximum;value++){
        if(frequency[value]>0){
            answer+=1LL*(frequency[value]-1)*value;
        }
    }
    for(int divisor=maximum;divisor>=1;divisor--){
        int anchor=0;
        for(int value=divisor;value<=maximum;value+=divisor){
            if(frequency[value]==0){
                continue;
            }
            if(anchor==0){
                anchor=value;
                continue;
            }
            int a=find(anchor);
            int b=find(value);
            if(a==b){
                continue;
            }
            if(size[a]<size[b]){
                swap(a,b);
            }
            // Descending divisors simulate maximum-weight Kruskal.
            parent[b]=a;
            size[a]+=size[b];
            answer+=divisor;
        }
    }
    cout<<answer<<'\n';
}