Overview

Let \(g\) be the GCD of the selected members’ skills. The team’s goodness is \(g \times (\text{number of members})\). To maximize this, for every possible \(g\), we count “how many people have a skill that is a multiple of \(g\)” and take the maximum.

Analysis

The team’s goodness is $\(\gcd(B_1,\dots,B_k)\times k\)$

Directly enumerating all teams “whose GCD is exactly \(g\)” is impossible (there are \(2^N\) subsets, and with \(N\le 10^6\) this is out of the question).

The key observation is as follows:

• If a team’s GCD is \(g\), then every member’s skill must be a multiple of \(g\) (because if the GCD is \(g\), all elements are divisible by \(g\)).
• Conversely, if “everyone’s skill is a multiple of \(g\)”, the GCD is not necessarily exactly \(g\) (it could be \(2g\), etc.). However, in this problem we don’t need the GCD to be exactly \(g\). We only want to find the maximum.

So how do we determine “the optimal number of members for a team with GCD \(g\)”?

• To form a team with GCD \(g\), the only candidates are “people whose skill is a multiple of \(g\)”
• The larger the number of members \(k\), the larger \(g\times k\) becomes (since \(g\) is fixed)
• Therefore, when \(g\) is fixed, it is optimal to select all participants whose skill is a multiple of \(g\) (maximizing the count)

In other words, for each \(g\): - \(s(g)=\) “number of participants whose skill is a multiple of \(g\)” - The candidate for the maximum goodness is \(g \times s(g)\)

The final answer is $\(\max_{g\ge 1}\; g \times s(g)\)$

Example: For \(A=[2,3,4,9]\) - \(g=1\): multiples — 4 people → \(1\times 4=4\) - \(g=2\): multiples — 2 people (2, 4) → \(2\times 2=4\) - \(g=3\): multiples — 2 people (3, 9) → \(3\times 2=6\) (maximum)

Algorithm

1. Since skill values are at most \(10^6\), count the frequency of each value in an array freq[x].
2. For each \(g=1,2,\dots,\text{maxA}\), enumerate multiples and sum up their counts: $\(s(g)=\sum_{m=g,2g,3g,\dots}\text{freq}[m]\)$
3. Compute \(g\times s(g)\) and update the maximum.

The enumeration of multiples can be done with a loop of the same form as the “Sieve of Eratosthenes”.

Complexity

• Time complexity: \(O\!\left(\sum_{g=1}^{M}\frac{M}{g}\right)=O(M\log M)\) (\(M=\max A_i \le 10^6\))
• Space complexity: \(O(M)\) (frequency array)

Implementation Notes

• Since \(N\) can be up to \(10^6\), input can become a bottleneck in Python. The code uses sys.stdin.buffer.read() and memoryview to read integers efficiently.

• freq is stored as array('I') (32-bit unsigned integers), which is more memory-efficient than a regular list.

• The loop range is limited to maxA (to avoid unnecessarily iterating over the entire range up to \(10^6\)).

  Source Code

import sys
from array import array

def main():
    data = sys.stdin.buffer.read()
    mv = memoryview(data)
    n = len(mv)
    idx = 0

    def read_int():
        nonlocal idx
        while idx < n and mv[idx] <= 32:
            idx += 1
        val = 0
        while idx < n and mv[idx] > 32:
            val = val * 10 + (mv[idx] - 48)
            idx += 1
        return val

    N = read_int()
    MAX_A = 10**6
    freq = array('I', [0]) * (MAX_A + 1)

    maxA = 0
    for _ in range(N):
        a = read_int()
        freq[a] += 1
        if a > maxA:
            maxA = a

    ans = 0
    freq_local = freq
    limit = maxA + 1
    for g in range(1, limit):
        s = 0
        for m in range(g, limit, g):
            s += freq_local[m]
        v = g * s
        if v > ans:
            ans = v

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.