Overview

This problem asks us to divide \(N\) students into connected components based on the relation “can cooperate if \(\gcd(W_i, W_j) \geq K\),” and find the maximum sum of specialty scores among all components.

Analysis

First, this problem can be reduced to managing connected components using a Union-Find (Disjoint Set Union) data structure. By treating cooperatable pairs as edges and merging the vertices connected by these edges, the final connected components will correspond to each group.

However, a naive approach of “checking if \(\gcd(W_i, W_j) \geq K\) for all pairs \((i, j)\) and adding an edge” would require checking \(O(N^2)\) pairs. This will result in a Time Limit Exceeded (TLE) since \(N \leq 2 \times 10^5\).

Here, we make an important observation.

Observation 1: Focus on common divisors

The condition \(\gcd(W_i, W_j) \geq K\) is equivalent to “there exists some integer \(d \geq K\) such that \(d\) divides both \(W_i\) and \(W_j\).”

In other words, for each \(d \geq K\), we can connect all “students whose specialty scores are multiples of \(d\)” into the same group. This is because any two such students share \(d\) as a common divisor, meaning their \(\gcd \geq d \geq K\), which makes them able to cooperate.

Conversely, if \(\gcd(W_i, W_j) \geq K\), then by setting \(d\) to be this \(\gcd\) value (which is \(\geq K\)), the two students will be connected in the group for multiples of \(d\). Thus, this method can represent all cooperative relationships without omission.

Observation 2: Grouping students with the same \(W\)

If there are multiple students with the same specialty score \(W\), they can cooperate with each other if \(W \geq K\) (since \(\gcd(W, W) = W \geq K\)), so we can merge them into one. It is sufficient to keep track of “one representative student” for each score value.

Algorithm

Similar to the Sieve of Eratosthenes, we iterate through multiples for each divisor \(d\).

1. Record Representatives: For each score value \(w\), record one representative student rep[w] who has this score. If there are multiple students with the same score and \(w \geq K\), merge them using Union.

2. Connect by Divisors: For each \(d = K, K+1, \ldots, M\) (where \(M\) is the maximum score), iterate through its multiples \(d, 2d, 3d, \ldots\). If we find representatives of students whose scores are multiples of \(d\), we Union all of them into a single set.

   • By scanning the multiples of \(d\) as \(d, 2d, 3d, \dots\) like a sieve, we can efficiently gather students whose scores are multiples of \(d\).

3. Calculate Sums: Finally, aggregate the students by their Union-Find roots to calculate the sum of specialty scores for each connected component. The maximum of these sums is the answer.

As a concrete example, consider the case where \(K=3\) and the scores are \(\{6, 9, 10\}\). - Multiples of \(d=3\) are \(6, 9\) \(\to\) the students with scores \(6\) and \(9\) are connected (since \(\gcd(6,9)=3 \geq 3\)). - As we increase \(d\), \(10\) does not connect with others because it shares no common divisor \(\geq 3\) with them.

Consequently, they are divided into the group \(\{6, 9\}\) (sum \(15\)) and the group \(\{10\}\) (sum \(10\)), and the answer is \(15\).

Complexity

Let \(M\) be the maximum value of the specialty scores (\(\leq 10^6\)).

• Time Complexity: In the sieve part, we perform \(M/d\) steps of iteration for each \(d\) from \(K\) to \(M\). By the sum of the harmonic series, this takes \(O\!\left(\sum_{d=K}^{M} \frac{M}{d}\right) = O(M \log M)\) time. Since the Union-Find operations take nearly constant time (inverse Ackermann function), the overall time complexity is \(O(M \log M + N)\).
• Space Complexity: \(O(M)\) for the representative array rep and \(O(N)\) for the Union-Find, resulting in a total of \(O(M + N)\).

Key Implementation Points

• Do not calculate \(\gcd\) directly: The core idea is to completely avoid calculating \(\gcd\) by focusing on the divisor \(d\) and connecting elements using a sieve. This avoids the \(O(N^2)\) pair-wise checks.

• Importance of grouping by representatives: By aggregating students with the same score into a single representative beforehand, the targets handled during the sieve scan are reduced to “unique score values,” preventing redundant Union operations.

• Starting point of \(d\): Since the common divisor \(d\) must be at least \(K\), the sieve loop starts from d = K. This naturally satisfies the condition \(\gcd \geq K\).

• Union-Find path compression: Performing path compression in the find function speeds up the operations. During the final summation, we also find the root using find(i) and add to it.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    W = [int(x) for x in data[2:2+n]]
    if n == 0:
        print(0)
        return
    M = max(W)
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        ra = find(a); rb = find(b)
        if ra != rb:
            parent[ra] = rb

    rep = [-1] * (M + 1)
    for i in range(n):
        w = W[i]
        if rep[w] == -1:
            rep[w] = i
        else:
            if w >= k:
                union(i, rep[w])

    # sieve: for each d >= k, union all students whose W is multiple of d
    for d in range(k, M + 1):
        first = -1
        m = d
        while m <= M:
            r = rep[m]
            if r != -1:
                if first == -1:
                    first = r
                else:
                    union(r, first)
            m += d

    total = [0] * n
    ans = 0
    for i in range(n):
        r = find(i)
        total[r] += W[i]
        if total[r] > ans:
            ans = total[r]
    print(ans)

main()

---

This editorial was generated by claude4.8opus-high.