$O(n² log n²)$ 最小生成树

关键观察

1. 染色花费：每个格子必须被染色一次，因此所有 $a_i$ 的和是必须的基础花费。

2. 移动花费：问题可以转化为构建一个连通图，其中：

   • 节点代表格子
   • 边的权重为 $lcm(a_i, a_j)$
   • 我们需要找到最小生成树，使得所有节点连通

3. 为什么是最小生成树：

   • 染色顺序可以看作是在图上遍历
   • 从已染色的节点（红色）移动到未染色节点（白色）的花费是lcm值
   • 最小生成树保证了所有节点以最小总花费连通

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;

int a[N], p[N];

struct node {
    int l, r, v;
} c[N * N];

int find(int x) {
    if (p[x] != x) return p[x] = find(p[x]);
    return p[x];
}

int lcm(int x, int y) {
    return x * y / __gcd(x, y);
}

bool cmp(node a, node b) {
    return a.v < b.v;
}

int main() {
    int n;
    cin >> n;
    long long ans = 0;
    
    // 初始化并查集和读取数据
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = i;
        ans += a[i];  // 每个格子至少染色一次
    }
    
    // 生成所有可能的边
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            c[++cnt] = {i, j, lcm(a[i], a[j])};
        }
    }
    
    // 按lcm值排序边
    sort(c + 1, c + cnt + 1, cmp);
    
    // Kruskal算法构建最小生成树
    for (int i = 1; i <= cnt; i++) {
        int l = c[i].l, r = c[i].r, v = c[i].v;
        int pa = find(l), pb = find(r);
        if (pa != pb) {
            ans += v;
            p[pa] = pb;
        }
    }
    
    cout << ans << '\n';
    return 0;
}