Overview

Given \(N\) participants, select a subset to maximize “GCD of the selected members’ skill levels × number of members.” The solution works by efficiently counting, for each divisor \(g\), how many skill levels are multiples of \(g\).

Analysis

Problem with the Naive Approach

There are \(2^N - 1\) possible subsets of \(1\) or more participants chosen from \(N\). Since \(N\) can be up to \(10^6\), enumerating all subsets is completely infeasible.

Key Insight

The key point is to fix the GCD value \(g\) and reason about it.

If we want the team’s GCD to be a multiple of \(g\), then every selected member’s skill level must be a multiple of \(g\). Conversely, selecting all members whose skill levels are multiples of \(g\) maximizes the count and is the most advantageous choice.

You might worry that “the GCD when selecting all such members might not be exactly \(g\) but some multiple \(g'\) of \(g\),” but this is not a problem. Here’s why:

• Since \(g' \geq g\), we have \(g' \times \text{count} \geq g \times \text{count}\).
• Since \(g'\) is a multiple of \(g\), the count of multiples of \(g'\) \(\leq\) the count of multiples of \(g\) (if collecting all multiples of \(g\) yields a GCD of \(g'\), then all of them are also multiples of \(g'\)).
• Therefore, when the loop enumerates \(g = g'\), the case is covered as \(g' \times (\text{count of multiples of } g')\).

Conclusion: For each \(g = 1, 2, \ldots, \max(A)\), compute “the count \(c_g\) of elements in \(A\) that are multiples of \(g\),” and the maximum value of \(g \times c_g\) is the answer.

Concrete Example

For \(A = [6, 12, 15, 30]\): - \(g = 6\): multiples are \(\{6, 12, 30\}\) → \(6 \times 3 = 18\) - \(g = 15\): multiples are \(\{15, 30\}\) → \(15 \times 2 = 30\) - \(g = 30\): multiples are \(\{30\}\) → \(30 \times 1 = 30\)

The answer is \(30\).

Algorithm

1. Build a frequency array: Create \(\text{cnt}[v]\) = the number of elements in \(A\) with value \(v\).
2. Compute the count of multiples for each \(g\): For \(g = 1, 2, \ldots, \max(A)\), enumerate multiples \(g, 2g, 3g, \ldots\) and sum up the \(\text{cnt}\) values to obtain the total count \(c_g\) of multiples of \(g\).
3. Update the answer: Find the maximum value of \(g \times c_g\).

Step 2 uses the same technique as the “Sieve of Eratosthenes,” enumerating multiples from each \(g\).

Complexity

Let \(M = \max(A)\).

• Time complexity: \(O(N + M \log M)\)
  • Building the frequency array takes \(O(N)\)
  • Enumerating multiples takes \(\sum_{g=1}^{M} \lfloor M/g \rfloor = O(M \log M)\) (harmonic series)
  • Since \(M, N \leq 10^6\), this is fast enough.
• Space complexity: \(O(M)\)
  • Size of the frequency array \(\text{cnt}\)

Implementation Notes

• First compute the maximum value \(M\) of \(A_i\) and allocate an array of size \(M+1\). If \(M\) is unnecessarily large, it wastes memory and time.

• In Python, reading input all at once with sys.stdin.buffer.read() speeds things up.

• The inner loop range(g, MAX_VAL + 1, g) is a standard Python technique for efficiently enumerating multiples using range.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    MAX_VAL = max(A)
    
    # cnt[v] = number of elements in A that equal v
    cnt = [0] * (MAX_VAL + 1)
    for a in A:
        cnt[a] += 1
    
    # For each g from 1 to MAX_VAL, count how many elements in A are divisible by g
    # This is the number of people we can pick whose GCD is a multiple of g
    # We want to find, for each g, the exact count of elements divisible by g,
    # then answer = max over g of (g * count_divisible_by_g)
    
    # Wait, but the GCD of chosen elements might be a multiple of g, not exactly g.
    # However, if we choose ALL elements divisible by g, their GCD is at least g,
    # so g * count is a lower bound. But the actual "togetherness" would be GCD * count >= g * count.
    # So taking max over all g of (g * count_divisible_by_g) would miss cases where
    # the actual GCD is larger. But those cases are covered by larger g values.
    # 
    # Actually, let's think again. For any subset S with GCD = d, the value is d * |S|.
    # The maximum subset with GCD being a multiple of d is all elements divisible by d,
    # and the GCD of that subset is some d' >= d. So the value d' * count >= d * count.
    # When we enumerate g = d', we get d' * (count of multiples of d') >= d' * count',
    # where count' might be smaller. 
    #
    # The key insight: for each possible GCD value g, the best we can do is pick all
    # elements divisible by g. The GCD of those elements is some g' >= g, and the value
    # is g' * count. But we'll also enumerate g', and get g' * count' where count' <= count
    # (since count' counts multiples of g' which is a subset of multiples of g).
    # The value g' * count = g' * count is what we'd get, and when we enumerate g = g',
    # we get g' * count' = g' * count (same count since all multiples of g that we picked
    # are also multiples of g'... no that's not right).
    #
    # Simpler argument: The optimal answer picks some subset with GCD = d. 
    # The best subset with GCD = d is to take all elements divisible by d (this maximizes count,
    # and GCD could be > d, but that's fine). When we enumerate g = d in our loop,
    # count_divisible_by_d >= the size of any subset with GCD = d, so g * count >= d * |subset|.
    # Actually the GCD of all elements divisible by d might be d' > d, giving value d' * count > d * count.
    # But we also enumerate g = d' and get d' * count_{d'} >= d' * count (since elements divisible
    # by d with GCD d' are all divisible by d', so count_{d'} >= count). 
    # Wait no, count_{d'} counts ALL elements divisible by d', which includes elements not divisible by d... 
    # but d' is a multiple of... no d' >= d doesn't mean d' is a multiple of d necessarily. 
    # Actually d' = GCD of all elements divisible by d, so d | d', meaning d' is a multiple of d.
    # So count_{d'} >= count_d. Hence d' * count_{d'} >= d' * count_d >= d * count_d.
    # So enumerating g = d' captures this case with an even better or equal value.
    #
    # Therefore, max over g of (g * count_divisible_by_g) gives the correct answer.
    
    ans = 0
    for g in range(1, MAX_VAL + 1):
        count = 0
        for multiple in range(g, MAX_VAL + 1, g):
            count += cnt[multiple]
        val = g * count
        if val > ans:
            ans = val
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.