Overview

We can model this problem as a graph where the students are vertices, and an edge exists between a pair of students \((i, j)\) if \(\gcd(W_i, W_j) \geq K\). We want to find the maximum sum of \(W_i\) over all connected components.

Utilizing the fact that the maximum value of \(W_i\) is small (up to \(10^6\)), we can group values that share a common divisor \(d \geq K\) using a Union-Find (Disjoint Set Union) data structure.

Analysis

Naively calculating \(\gcd(W_i, W_j)\) for all pairs of students would require

\(O(N^2)\)

pairs in the worst case. Since \(N \leq 2 \times 10^5\), this will not run within the time limit.

Instead of focusing on the individual students, we focus on the “specialty scores” themselves.

For two values \(x\) and \(y\), the condition

\(\gcd(x, y) \geq K\)

is equivalent to saying that:

There exists a common divisor \(d\) of \(x\) and \(y\) such that \(d \geq K\).

In other words, for any \(d \geq K\), all values that are multiples of \(d\) can directly cooperate with each other.

For example, if \(K = 3\), the values \(6\) and \(15\) are both multiples of \(3\), so

\(\gcd(6, 15) = 3 \geq K\)

which means they belong to the same component.

Therefore, for each \(d = K, K+1, \ldots\), we can use Union-Find to group all multiples of \(d\) that exist in the input.

However, we must be careful when the same value appears multiple times.

• If \(w \geq K\):
  Students with the same score \(w\) will belong to the same group because \(\gcd(w, w) = w \geq K\). Thus, we add \(w \times \text{freq}[w]\) to the sum of their component.

• If \(w < K\):
  For any value \(x\), we have \(\gcd(w, x) \leq w < K\), meaning students with score \(w\) cannot cooperate with anyone. Even students with the same score \(w\) cannot cooperate with each other because \(\gcd(w, w) = w < K\). Thus, each such student forms their own isolated component, and the candidate for the maximum sum from these is simply \(w\).

Algorithm

First, we record the frequency of each specialty score \(w\) in freq[w].

Let \(A\) be the maximum specialty score. We initialize a Union-Find for the values \(1, 2, \ldots, A\).

Next, for each \(d = K, K+1, \ldots, A\), we iterate through the multiples of \(d\).

for (int d = K; d <= A; d++) {
    int first = -1;
    for (int m = d; m <= A; m += d) {
        if (freq[m] == 0) continue;
        if (first == -1) first = m;
        else dsu.unite(first, m);
    }
}

Here, we group all multiples of \(d\) that exist in the input into the same set.

Unioning all pairs of multiples directly would be too slow, but we can merge them into the same set efficiently by unioning each multiple with the first encountered multiple first.

For example, if \(10, 15, 20\) exist as multiples of \(d = 5\), we can:

• Union \(10\) and \(15\)
• Union \(10\) and \(20\)

This merges \(10, 15, 20\) into the same set.

After that, we calculate the sum for each value \(w\).

• If \(w < K\), it forms an isolated component, so the candidate answer is \(w\).
• If \(w \geq K\), we find the representative (root) of \(w\) in the Union-Find, and add \(w \times \text{freq}[w]\) to that component’s sum.

Finally, we output the maximum sum over all components.

Complexity

Let \(A = \max W_i\).

Since we iterate through the multiples of each \(d\), the total number of operations is approximately:

\(\sum_{d=K}^{A} \frac{A}{d} \leq A \log A\)

Since the Union-Find operations take nearly constant time, the complexities are:

• Time Complexity: \(O(N + A \log A)\)
• Space Complexity: \(O(A)\)

Given the constraint \(A \leq 10^6\), this is fast enough.

Implementation Details

By storing the frequency in freq[w], we can process students with the same score together.

However, since students with \(w < K\) cannot cooperate even with others who have the same score \(w\), we must not group these freq[w] students together. In the code, we handle \(w < K\) as isolated components and simply update ans = max(ans, (long long)w) as follows:

if (w < K) {
    ans = max(ans, (long long)w);
} else {
    int r = dsu.find(w);
    sum[r] += 1LL * w * freq[w];
}

Also, the maximum possible sum can be up to \(2 \times 10^5 \times 10^6 = 2 \times 10^{11}\), so we must use long long to prevent integer overflow.

Source Code

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

struct DSU {
    vector<int> parent, sz;

    DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    const int LIM = 1000000;
    vector<int> freq(LIM + 1, 0);

    int A = 0;
    for (int i = 0; i < N; i++) {
        int w;
        cin >> w;
        freq[w]++;
        A = max(A, w);
    }

    DSU dsu(A + 1);

    for (int d = K; d <= A; d++) {
        int first = -1;
        for (int m = d; m <= A; m += d) {
            if (freq[m] == 0) continue;
            if (first == -1) first = m;
            else dsu.unite(first, m);
        }
    }

    vector<long long> sum(A + 1, 0);
    long long ans = 0;

    for (int w = 1; w <= A; w++) {
        if (freq[w] == 0) continue;

        if (w < K) {
            ans = max(ans, (long long)w);
        } else {
            int r = dsu.find(w);
            sum[r] += 1LL * w * freq[w];
        }
    }

    for (long long x : sum) {
        ans = max(ans, x);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.