概要

選んだメンバーのスキルの最大公約数（GCD）を \(g\) とすると、チームの良さは \(g \times (\text{人数})\) です。これを最大化するために、全ての \(g\) について「\(g\) の倍数が何人いるか」を数えて最大値を取ります。

考察

チームの良さは $\(\gcd(B_1,\dots,B_k)\times k\)$ です。

ここで「GCD がちょうど \(g\) のチーム」を直接全探索するのは不可能です（部分集合は \(2^N\) 通り、\(N\le 10^6\) なので論外）。

重要な観察は次の通りです。

• あるチームの GCD が \(g\) であるなら、チーム内の全員のスキルは 必ず \(g\) の倍数 である
  （GCD が \(g\) なら全要素が \(g\) で割り切れるため）。
• 逆に、「全員が \(g\) の倍数」であれば、GCD は \(g\) とは限りません（\(2g\) などの可能性がある）。
  しかし、この問題では GCD が厳密に \(g\) である必要はありません。最大値を求めたいだけです。

では「GCD が \(g\) のチームの最適な人数」はどう決めればよいでしょうか？

• GCD が \(g\) のチームを作るには、候補は「\(g\) の倍数の人」だけ
• 人数 \(k\) を増やすほど \(g\times k\) は増える（\(g\) は固定）
• よって、\(g\) を固定したときは \(g\) の倍数の参加者を全員選ぶのが最適（人数最大）

つまり、各 \(g\) について - \(s(g)=\)「スキルが \(g\) の倍数の参加者数」 - 良さの最大候補は \(g \times s(g)\)

最終的な答えは $\(\max_{g\ge 1}\; g \times s(g)\)$ になります。

例：\(A=[2,3,4,9]\) のとき
- \(g=1\): 倍数は4人 → \(1\times 4=4\)
- \(g=2\): 倍数は2人（2,4）→ \(2\times 2=4\)
- \(g=3\): 倍数は2人（3,9）→ \(3\times 2=6\)（最大）

アルゴリズム

1. スキル値は最大でも \(10^6\) なので、値ごとの個数を配列 freq[x] に数え上げる。
2. 各 \(g=1,2,\dots,\text{maxA}\) について、倍数を列挙して個数を合計する： $\(s(g)=\sum_{m=g,2g,3g,\dots}\text{freq}[m]\)$
3. \(g\times s(g)\) を計算し、最大値を更新する。

倍数の列挙は「エラトステネスの篩」と同じ形のループで行えます。

計算量

• 時間計算量: \(O\!\left(\sum_{g=1}^{M}\frac{M}{g}\right)=O(M\log M)\)（\(M=\max A_i \le 10^6\)）
• 空間計算量: \(O(M)\)（頻度配列）

実装のポイント

• \(N\) が最大 \(10^6\) なので、Python では入力がボトルネックになりやすいです。コードでは sys.stdin.buffer.read() と memoryview で高速に整数を読み取っています。

• freq は array('I')（32-bit 符号なし整数）で持ち、通常の list よりメモリ効率を良くしています。

• ループ範囲は maxA までに抑えています（無駄に \(10^6\) 全域を回さない）。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。