Overview

We can model this problem as a graph where each student is a vertex, and an edge exists between a pair of students if \(\gcd(W_i, W_j) \geq K\). The task is to find the maximum sum of \(W_i\) within any connected component.

Analysis

Naively calculating \(\gcd(W_i, W_j)\) for all pairs of students would require \(O(N^2)\) operations.
Since \(N \leq 2 \times 10^5\), this will obviously not run in time.

The key observation is as follows.

For any two values \(x\) and \(y\),

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

is equivalent to:

“There exists some integer \(d \geq K\) that divides both \(x\) and \(y\).”

In other words, for any \(d \geq K\), values that are multiples of \(d\) will belong to the same connected component.

For example, consider \(K = 3\) and the values \(6, 10, 15\).

• \(6\) and \(15\) are both multiples of \(3\), so they are connected.
• \(10\) and \(15\) are both multiples of \(5\), so they are connected.
• \(6\) and \(10\) are not directly connected, but they are indirectly connected via \(15\).

Thus, these three values belong to the same group (component).

In this way, by treating each “value” as a vertex and merging values that share a common divisor \(d \geq K\) using a Union-Find (Disjoint Set Union) data structure, we can find the connected components.

We also need to be careful when the same value appears multiple times.

• If \(w \geq K\):
  The \(\gcd\) of the same value is \(w \geq K\), so students with the same value will be connected to each other.
  Therefore, we can treat them from the start as a single component with a total sum of \(cnt[w] \times w\).

• If \(w < K\):
  The \(\gcd\) of \(w\) with any other value is at most \(w\), which is strictly less than \(K\).
  This means even if there are multiple students with the same value, they cannot connect to each other, and each remains as an independent component.
  The total power of such a component is simply \(w\).

Algorithm

First, we count the number of occurrences of each value \(w\) as cnt[w].
Let the maximum value be \(M = \max W_i\).

Special Cases

Case \(K = 1\)

The greatest common divisor of any two positive integers is always at least \(1\).

Therefore, all students belong to the same connected component, and the answer is:

\[ \sum_i W_i \]

Case \(K > M\)

For any two values, their greatest common divisor is at most \(M\).
Thus, there are no pairs such that \(\gcd(W_i, W_j) \geq K\).

Since everyone forms an independent component, the answer is the maximum individual score, \(M\).

General Case

We initialize a Union-Find data structure for the values \(1, 2, \ldots, M\).

We set the initial state for each value \(i\).

• If \(i < K\) and cnt[i] > 0:
  All students with this value are isolated, so \(i\) is a candidate for the maximum sum.

• If \(i \geq K\) and cnt[i] > 0:
  Students with the same value will connect to each other, so we initialize the sum of this component as:

$\( cnt[i] \times i \)$

Next, for each \(d = K, K+1, \ldots, M\), we examine the multiples of \(d\).

We merge all values that are multiples of \(d\) and actually exist in the input into the same component.

Specifically:

d, 2d, 3d, ...

We inspect the multiples in order. The first existing value we find will be the reference base, and we Union any subsequent existing multiples with this base.

This ensures that “values sharing a common divisor \(d \geq K\)” are grouped into the same component.

During the Union operation, we also maintain the sum of each component.
Whenever we merge components, we update the overall answer with the new total sum.

By performing this process for all \(d \geq K\), all valid connected components will be correctly formed.

Complexity

Let \(M = \max W_i\).

Since we examine the multiples of each \(d\), the total number of loop iterations is approximately:

\[ \sum_{d=K}^{M} \frac{M}{d} \]

which is at most \(O(M \log M)\).

Since Union-Find operations run in near-constant time, the overall algorithm is sufficiently fast.

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

Implementation Details

In the Union-Find, we store the total power of each connected component as comp[root] for each root.

When merging, we update the sum as follows:

comp[new_root] = comp[root1] + comp[root2]

and then update the overall answer with this new value.

Also, note that values \(i < K\) cannot be connected to any other values.
In particular, even if the same value appears multiple times, they will not connect to each other if \(i < K\).
Therefore, you must not set the component’s sum to cnt[i] * i for \(i < K\).

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    W = data[2:]

    M = max(W)

    if K == 1:
        print(sum(W))
        return

    if K > M:
        print(M)
        return

    cnt = [0] * (M + 1)
    for w in W:
        cnt[w] += 1

    parent = list(range(M + 1))
    comp = [0] * (M + 1)

    ans = 0

    for i in range(1, K):
        if cnt[i]:
            ans = i

    for i in range(K, M + 1):
        if cnt[i]:
            v = cnt[i] * i
            comp[i] = v
            if v > ans:
                ans = v

    p = parent
    s = comp
    c = cnt

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

    for d in range(K, M + 1):
        base = 0
        for m in range(d, M + 1, d):
            if c[m]:
                if base == 0:
                    base = find(m)
                else:
                    r = find(m)
                    if base != r:
                        if s[base] < s[r]:
                            base, r = r, base
                        p[r] = base
                        ns = s[base] + s[r]
                        s[base] = ns
                        s[r] = 0
                        if ns > ans:
                            ans = ns

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.