Overview

Given \(N\) participants, select some of them to maximize “GCD of the selected members’ skill levels \(\times\) number of selected members.”

Analysis

Why a naive approach doesn’t work There are \(2^N - 1\) total ways to select participants. Trying to enumerate all of them with the constraint \(N \le 10^6\) would take an astronomical amount of time and result in a Time Limit Exceeded (TLE) verdict.

Changing perspective: Fix the “GCD” Instead of thinking about which combination of members to select, let’s assume “the team’s GCD will be \(g\)” and work from there. For the team’s GCD to be \(g\), all selected members’ skill levels must be multiples of \(g\).

Since the team’s cohesion is calculated as “\(g \times\) number of members,” if \(g\) is fixed, the more members the better. Therefore, it is optimal to select all participants whose skill levels are multiples of \(g\).

You might wonder, “But if we select all of them, won’t the actual GCD become larger than \(g\)?” For example, suppose the participants’ skill levels are \(A = [4, 8, 12]\). If we set \(g=2\) and select all multiples of 2, we pick \(4, 8, 12\) (3 people), and the actual GCD is \(4\). However, there’s no need to worry. In that case, when we later examine \(g=4\), the value “\(4 \times 3\)” will be correctly computed, and the maximum will be updated accordingly. In other words, for every \(g\), we compute “\(g \times (\text{number of multiples of } g \text{ in } A)\)” and take the maximum — this gives us the correct answer.

Algorithm

1. Let \(M\) be the maximum value among the skill levels \(A_i\).
2. Count how many participants have each skill level and record this in an array count.
3. Enumerate all candidate GCD values \(g\) from \(1\) to \(M\).
4. For each \(g\), find how many elements in \(A\) are multiples of \(g\). This can be computed by summing count[g] + count[2g] + count[3g] + ....
5. Compute “\(g \times (\text{number of people with multiples of } g)\)” and update the maximum.
6. Output the final maximum.

Complexity

• Time complexity: \(O(N + M \log M)\)
  • Tallying the \(A_i\) values takes \(O(N)\).
  • The total number of operations for counting multiples is \(\frac{M}{1} + \frac{M}{2} + \frac{M}{3} + \dots + \frac{M}{M}\). This is known as the “harmonic series” and is known to be approximately proportional to \(M \log M\).
  • Therefore, the overall complexity is \(O(N + M \log M)\), which runs sufficiently fast even for \(N, M \le 10^6\).
• Space complexity: \(O(N + M)\)
  • \(O(N)\) is used to store the input data, and \(O(M)\) is used for the array count that records the frequency of each element.

Implementation Notes

In Python, naively using for loops to sum up multiples can result in long execution times due to loop overhead. The solution code leverages Python’s list slicing with sum(count[g::g]). This extracts only the elements at indices that are multiples of \(g\) from the count array using internally optimized processing, computing the sum all at once, leading to a significant speedup. Additionally, using sys.stdin.read().split() to read all input at once is a standard technique for speeding up I/O in competitive programming when dealing with large inputs.

Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    A = [int(x) for x in input_data[1:]]
    
    M = max(A)
    count = [0] * (M + 1)
    for a in A:
        count[a] += 1
        
    ans = 0
    for g in range(1, M + 1):
        c = sum(count[g::g])
        res = c * g
        if res > ans:
            ans = res
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.