Overview

This is a problem where you select participants to form a team and find the maximum “cohesion” of the team (the greatest common divisor of the members’ skill levels × the number of members).

Analysis

A naive approach would be to try all subsets, but since \(N\) can be up to \(10^6\), trying all \(2^N\) possibilities is infeasible.

The key observation is that in an optimal team, the greatest common divisor \(g\) divides the skill levels of all team members. In other words, all team members must have skill levels that are multiples of \(g\).

Furthermore, when \(g\) is fixed, including all participants whose skill levels are multiples of \(g\) guarantees that the greatest common divisor is at least \(g\). The team size in this case equals the number of people whose skill levels are multiples of \(g\).

Algorithm

1. Create an array count that counts the frequency of each value
2. For each number \(g\), compute the total count of values that are multiples of \(g\): multiples[g]
3. For each \(g\), compute the cohesion \(g \times \text{multiples}[g]\) and find the maximum

This method efficiently computes the answer for all possible values of \(g\). It suffices to check \(g\) from \(1\) up to the maximum value.

Complexity

• Time complexity: \(O(M \log M)\) (where \(M\) is the maximum value in the input)
• Space complexity: \(O(M)\)

Implementation Details

• Find the maximum input value max_val to determine the array size

• Create a count array to store the frequency of each value

• In the nested loop that checks multiples of each \(g\), the inner loop accesses \(j = i, 2i, 3i, \ldots\), making it efficient by skipping non-multiples

• For each \(g\), compute \(g \times \text{multiples}[g]\) and update the maximum

  Source Code

import sys
import math

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    max_val = max(A) if A else 0
    count = [0] * (max_val + 1)
    for a in A:
        count[a] += 1
        
    multiples = [0] * (max_val + 1)
    for i in range(1, max_val + 1):
        for j in range(i, max_val + 1, i):
            if count[j] > 0:
                multiples[i] += count[j]
                
    ans = 0
    for g in range(1, max_val + 1):
        if multiples[g] > 0:
            candidate = g * multiples[g]
            if candidate > ans:
                ans = candidate
                
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.