Overview

This problem asks us to find the maximum sum of scores among all connected components (groups) formed by connecting students under the condition that the greatest common divisor (\(\gcd\)) of their specialized scores \(W_i\) is at least \(K\).

Analysis

Pitfalls of a Naive Approach

The simplest approach is to check if \(\gcd(W_i, W_j) \ge K\) for all pairs of students \((i, j)\), build a graph by adding edges between pairs that satisfy this condition, and then find the connected components. However, since the number of students \(N\) is up to \(2 \times 10^5\), checking all pairs would result in a time complexity of \(O(N^2)\), which will exceed the time limit (TLE).

Key Observations for Optimization

1. Students with Scores Less Than \(K\)

For any student \(i\) with a score \(W_i\) less than \(K\), the greatest common divisor with any other student \(j\) satisfies \(\gcd(W_i, W_j) \le W_i < K\). Thus, they cannot cooperate with anyone. Therefore, these students will always form a “group of size 1” containing only themselves. The total score of such a group is simply \(W_i\), so it is sufficient to keep track of the maximum score among all students with \(W_i < K\).

2. Connectivity of Students with Scores of at Least \(K\)

Let’s consider students with scores of at least \(K\). If two scores \(x, y \ge K\) share a common divisor \(g \ge K\) (meaning both \(x\) and \(y\) are multiples of \(g\)), their greatest common divisor \(\gcd(x, y)\) is guaranteed to be at least \(g\): $\(\gcd(x, y) \ge g \ge K\)\( Therefore, we can say that **"scores sharing a common divisor \)g \ge K$ can directly cooperate with each other (i.e., belong to the same group).“**

Let \(M\) (\(M \le 10^6\)) be the maximum score. For each \(g \ge K\), we can correctly group the students by merging (unioning) all existing multiples of \(g\) together.

Algorithm

This problem can be solved efficiently by utilizing a Union-Find (Disjoint Set Union) data structure and the properties of the harmonic series.

1. Classification and Aggregation of Scores

   • Record the maximum score among students with \(W_i < K\) as max_less_than_K.
   • For students with \(W_i \ge K\), count the occurrences of each score in count and calculate the sum of scores for each value in sum_W. (Students with the exact same score will always belong to the same group, so we can group them together beforehand).

2. Union-Find Initialization

   • Create a Union-Find data structure with elements from \(0\) to \(M\).
   • Set the initial weight (total score of the group) of each element \(x\) to sum_W[x].

3. Merging Multiples

   • Iterate the candidate common divisor \(g\) from \(K\) to \(M\).
   • For each \(g\), iterate through its multiples \(x = g, 2g, 3g, \ldots \le M\).
   • When the first existing score (count[x] > 0) is found, let it be first. For any subsequent existing scores \(x\) found, merge (unite) them with first in the Union-Find. When merging, also sum up the weights (total scores) of the groups.

4. Finding the Maximum Value

   • Find the maximum weight of any group in the Union-Find among all scores of at least \(K\), and let it be max_ge_K.
   • The final answer is max(max_less_than_K, max_ge_K).

Complexity

• Time Complexity: \(O(N + M \log M)\)

  • Reading the input and aggregating the scores takes \(O(N)\) time.
  • The number of iterations in the multiple-merging step is bounded by the sum of the harmonic series: $\(\sum_{g=K}^{M} \frac{M}{g} \approx M \log \left(\frac{M}{K}\right)\)\( When \)M \le 10^6\(, this value is at most a few million operations. Combined with the Union-Find operations (which are nearly \)O(1)$), this easily runs well within the time limit.

• Space Complexity: \(O(M)\)

  • Since we maintain arrays up to the maximum score \(M\) (such as count and sum_W) along with the Union-Find arrays, the space complexity is \(O(M)\).

Implementation Points

• Equipping Union-Find with Weights

  • In addition to the standard Union-Find, we maintain a weight array that stores the “sum of scores” for each group.
  • When performing unite(x, y), we add the weights of the roots (e.g., weight[ry] += weight[rx]). This allows us to correctly and quickly update the total score of the merged group.

• Grouping Identical Scores

  • If multiple students have the same score, treating them individually in the Union-Find would result in \(N\) elements, which is inefficient. By using the score values themselves as the elements of the Union-Find and pre-aggregating their weights, we can limit the number of elements to at most \(M \le 10^6\).

    Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

struct UnionFind {
    vector<int> parent;
    vector<long long> weight;
    UnionFind(int n, const vector<long long>& init_weight) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        weight = init_weight;
    }
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            parent[rx] = ry;
            weight[ry] += weight[rx];
        }
    }
    long long get_weight(int x) {
        return weight[find(x)];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<int> W(N);
    int M = 0;
    long long max_less_than_K = 0;
    for (int i = 0; i < N; ++i) {
        cin >> W[i];
        if (W[i] > M) M = W[i];
        if (W[i] < K) {
            if (W[i] > max_less_than_K) {
                max_less_than_K = W[i];
            }
        }
    }

    vector<long long> sum_W(M + 1, 0);
    vector<int> count(M + 1, 0);
    for (int i = 0; i < N; ++i) {
        if (W[i] >= K) {
            sum_W[W[i]] += W[i];
            count[W[i]]++;
        }
    }

    UnionFind uf(M + 1, sum_W);

    for (int g = K; g <= M; ++g) {
        int first = -1;
        for (int x = g; x <= M; x += g) {
            if (count[x] > 0) {
                if (first == -1) {
                    first = x;
                } else {
                    uf.unite(first, x);
                }
            }
        }
    }

    long long max_ge_K = 0;
    for (int v = K; v <= M; ++v) {
        if (count[v] > 0) {
            max_ge_K = max(max_ge_K, uf.get_weight(v));
        }
    }

    long long ans = max(max_less_than_K, max_ge_K);
    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.