CF2172F Cluster Computing System 题解

sunqihuan · 2025-11-27 14:16:22 · 题解

因为参与求最大公约数的数越多，最大公约数越小，所以一定是尽量跨度大，所以要么连到 1 要么连到 n，预处理前后缀最大公约数后取最小值即可。但是要注意一点，就是第一个点和最后一个点只能取一个连到对方因为我们这里是要最小生成树，取一个已经可以连通就不要算两遍。这个方案可以保证正确因为最后所有点要么连到 1 上要么连到 n 上，而 1 和 n 是相连的，所以一定连通。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 5;

int n, a[N], g[N], g2[N], res;

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    g[1] = a[1];
    for (int i = 2; i <= n; i ++ ) g[i] = __gcd(a[i], g[i - 1]);
    g2[n] = a[n];
    for (int i = n - 1; i >= 1; i -- ) g2[i] = __gcd(a[i], g2[i + 1]);
    for (int i = 2; i < n; i ++ ) res += min(g[i], g2[i]);
    cout << res + min(g[n], g2[1]) << endl;
    return 0;
}