GCD and MST

Created by LXC on Fri Jul 21 11:13:34 2023

https://codeforces.com/problemset/problem/1513/D

ranting: 2000

tag: constructive algorithms, dsu, graphs, greedy, number theory, sortings

problem

给出n个顶点的无向图，顶点的编号从1到n，每个顶点都有一个权值$a_i$。

对于编号为i的点与编号为i+1的点连接一条边权为p的边。

此外对于$gcd(a_i, a_{i+1}, a_{i+2}, \dots, a_{j}) = min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$的编号i和j之间连接一条边权为$min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$的边。

求最小生成树的边权和

solution

如果我们考虑从a中最小值开始向左右两边扩展，会发现形成的区间的最小值是固定的。而对于区间的gcd是否等于区间最小值，只需要在扩展时判断元素是否为区间最小值的倍数。如果不是最小值的倍数则停止在这个方向上的扩展；如果是最小值的倍数则可以让这个扩展元素与最小值的元素连接一条边。

我们发现如果从小到大选择a中元素，可以完美契合求最小生成树的krushkal算法。每次选择最小边加入MST。

为了避免形成环，可以使用并查集判断环，用$con_i$代表i和i+1是否连通，由于是从中心最小值扩展，判断每个扩展元素是否与中心连接，若连接则当前边会形成环。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, p;
    cin >> n >> p;
    vector<int> a(n);
    set<pair<int, int>> st;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        st.emplace(a[i], i);
    }
    ll ans = 0;
    vector<int> con(n, 0);  // con[i] i是否与右侧某个相连
    for (auto [i, j] : st) {
        if (i >= p)
            continue;
        int p = j;
        while (p > 0) {
            if (con[p - 1] || a[p - 1] % i)
                break;
            con[p - 1] = 1;
            ans += i;
            p--;
        }
        p = j;
        while (p < n - 1) {
            if (con[p] || a[p + 1] % i)
                break;
            con[p] = 1;
            ans += i;
            p++;
        }
    }
    for (int i = 0; i < n - 1; i++) {
        if (!con[i])
            ans += p;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}