GCD Maximum Spanning Tree の解説

制約から調和級数をエスパーする。

あとは約数作れる組み合わせを大きい順で試していってDSUで管理しつつ全域木を作ればOK

fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let amax = a.iter().max().unwrap() + 10;
    let mut map = vec![usize::MAX; amax];
    for (idx, &num) in a.iter().enumerate() {
        map[num] = idx;
    }
    let mut uf = Dsu::new(n);
    let mut ans = 0;
    for num in (1..amax).rev() {
        let mut now = num;
        let mut v = vec![];
        loop {
            if now >= amax {
                break;
            }
            if map[now] != usize::MAX {
                v.push(map[now]);
            }
            now += num;
        }
        if v.len() <= 1 {
            continue;
        }
        for i in 0..v.len() - 1 {
            let a = v[i];
            let b = v[i + 1];
            if uf.same(a, b) {
                continue;
            }
            uf.merge(a, b);
            ans += num;
        }
    }
    println!("{}", ans);
}