Tóm tắt đề bài

Cho đồ thị đầy đủ \(n\) đỉnh, mỗi đỉnh \(i\) có một giá trị \(a_i\). Trọng số của cạnh nối giữa hai đỉnh \(i\) và \(j\) được tính bằng công thức: \(w(i, j) = 123456 - \text{GCD}(a_i, a_j)\). Yêu cầu tìm tổng trọng số của cây khung nhỏ nhất (MST) của đồ thị này.

Phân tích

• Công thức trọng số: \(w(i, j) = 123456 - \text{GCD}(a_i, a_j)\).
• Để tối thiểu hóa tổng trọng số của cây khung, ta cần tối đa hóa tổng các giá trị \(\text{GCD}(a_i, a_j)\) của các cạnh trong cây khung đó.
• Gọi \(C = 123456\). Một cây khung có \(n-1\) cạnh. Tổng trọng số cây khung là:
  
  \[ \sum_{(i, j) \in \text{MST}} (C - \text{GCD}(a_i, a_j)) = (n-1) \times C - \sum_{(i, j) \in \text{MST}} \text{GCD}(a_i, a_j) \]
• Bài toán trở thành: Tìm một cây khung sao cho tổng các \(\text{GCD}\) của các cạnh là lớn nhất.
• Ràng buộc: \(n \le 50,000\) và \(a_i \le 10^5\). Đồ thị đầy đủ có \(O(n^2)\) cạnh, nên ta không thể sử dụng các thuật toán MST thông thường như Kruskal hay Prim trực tiếp trên mọi cạnh. Tuy nhiên, giá trị \(a_i\) khá nhỏ, đây là gợi ý để ta khai thác các ước chung.

Hướng giải quyết

Ý tưởng chính

Thay vì xét từng cạnh, ta xét từng giá trị có thể là \(\text{GCD}\) từ lớn đến nhỏ. Với mỗi giá trị \(g\) từ \(\max(a_i)\) xuống \(1\):

• Tìm tất cả các đỉnh \(u\) có \(a_u\) là bội của \(g\).
• Nếu có nhiều hơn một đỉnh như vậy, ta cố gắng nối các đỉnh này lại với nhau bằng các cạnh có "tiềm năng" nhận \(g\) làm \(\text{GCD}\) (hoặc một bội của \(g\)).
• Sử dụng cấu trúc dữ liệu Disjoint Set Union (DSU) để quản lý các thành phần liên thông. Nếu hai đỉnh thuộc hai thành phần liên thông khác nhau, ta nối chúng và cộng \(g\) vào tổng \(\text{GCD}\).

Các bước thực hiện

1. Lưu vị trí (chỉ số) của các giá trị \(a_i\) vào một mảng các vector id[val].
2. Khởi tạo DSU cho \(n\) đỉnh.
3. Duyệt \(g\) từ \(mx = \max(a_i)\) giảm dần về \(1\):
   • Tập hợp tất cả các chỉ số \(x\) sao cho \(a_x\) là bội của \(g\) (tức là \(a_x \in \{g, 2g, 3g, \dots\}\)).
   • Duyệt qua danh sách các chỉ số này, thử nối các đỉnh liên tiếp \((s_j, s_{j+1})\) bằng DSU.
   • Nếu dsu.join(s[j], s[j+1]) trả về true (nghĩa là hai đỉnh này trước đó chưa liên thông), ta đã thêm được một cạnh vào cây khung với \(\text{GCD}\) ít nhất là \(g\).
   • Lưu ý: Vì ta duyệt \(g\) từ lớn đến nhỏ, cạnh đầu tiên nối hai thành phần liên thông sẽ có \(g\) lớn nhất có thể, đảm bảo tính tối ưu của thuật toán Kruskal.
4. Kết quả cuối cùng là \((n-1) \times 123456 - (\text{tổng các } g \text{ đã nối})\).

Độ phức tạp

• Thời gian: \(O(V \log V + n \log V)\) với \(V = \max(a_i)\). Việc duyệt qua các bội số của \(g\) tương tự như sàng Eratosthenes, tốn \(O(V \log V)\). Mỗi đỉnh được xét trong danh sách bội số của các ước của nó, số lượng ước của một số không quá lớn.
• Bộ nhớ: \(O(n + V)\) để lưu trữ DSU và danh sách các chỉ số.

Code tham khảo

#include <bits/stdc++.h>
#define int long long
using namespace std;

// Cấu trúc dữ liệu Disjoint Set Union để quản lý các thành phần liên thông
struct DisJointSet {
    int n;
    vector<int> par;

    DisJointSet(int _n) {
        n = _n;
        par.assign(n + 5, -1);
    }

    int getpar(int u) {
        return (par[u] < 0) ? u : par[u] = getpar(par[u]);
    }

    // Trả về true nếu nối thành công hai thành phần khác nhau
    bool join(int u, int v) {
        u = getpar(u);
        v = getpar(v);
        if (u == v) return false;
        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};

const int N = 1e5 + 5;
vector<int> s;
vector<int> id[N]; // id[v] lưu danh sách các chỉ số i mà a[i] = v
int n;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if (!(cin >> n)) return 0;

    int mx = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        id[x].push_back(i);
        mx = max(mx, x);
    }

    DisJointSet dsu(n);
    int total_gcd = 0;
    int edges_count = 0;

    // Duyệt GCD từ lớn đến nhỏ để tối đa hóa tổng GCD
    for (int i = mx; i >= 1; i--) {
        s.clear();
        // Tìm tất cả các đỉnh có nhãn là bội của i
        for (int j = i; j <= mx; j += i) {
            for (int x : id[j]) {
                s.push_back(x);
            }
        }

        // Thử nối các đỉnh này lại với nhau
        for (int j = 0; j + 1 < (int)s.size(); j++) {
            if (dsu.join(s[j], s[j + 1])) {
                total_gcd += i;
                edges_count++;
            }
        }
        // Nếu đã đủ n-1 cạnh thì có thể dừng sớm
        if (edges_count == n - 1) break;
    }

    // Kết quả: (n-1) * 123456 - tổng GCD
    int ans = 123456 * (n - 1) - total_gcd;
    cout << ans;

    return 0;
}