概要

\(N\) 人の参加者から部分集合を選び、「選んだメンバーのスキルレベルのGCD × 人数」を最大化する問題です。各約数 \(g\) について \(g\) の倍数であるスキルレベルの個数を高速に数え上げることで解きます。

考察

素朴なアプローチの問題点

\(N\) 人の参加者から \(1\) 人以上を選ぶ部分集合は \(2^N - 1\) 通りあります。\(N\) が最大 \(10^6\) なので、全ての部分集合を列挙するのは到底不可能です。

重要な気づき

まず、GCDの値 \(g\) を固定して考えることがポイントです。

もしチームのGCDが \(g\) の倍数であってほしいなら、選ぶメンバー全員のスキルレベルが \(g\) の倍数でなければなりません。逆に、\(g\) の倍数であるスキルレベルを持つメンバーを全員選ぶのが、人数を最大化でき最も有利です。

ここで「全員選んだときのGCDは \(g\) ちょうどではなく \(g\) の倍数 \(g'\) かもしれない」と心配になりますが、問題ありません。なぜなら：

• \(g' \geq g\) なので、\(g' \times \text{人数} \geq g \times \text{人数}\) です。
• \(g'\) は \(g\) の倍数なので、\(g' \) の倍数の個数 \(\geq\) \(g\) の倍数の個数です（\(g\) の倍数を全部集めたらそのGCDが \(g'\) になったということは、それらは全て \(g'\) の倍数でもある）。
• よって、ループで \(g = g'\) を列挙したときに \(g' \times (\text{\)g’\(の倍数の個数})\) としてこのケースはカバーされます。

結論: 各 \(g = 1, 2, \ldots, \max(A)\) に対して「\(A\) の中で \(g\) の倍数である要素の個数 \(c_g\)」を求め、\(g \times c_g\) の最大値が答えです。

具体例

\(A = [6, 12, 15, 30]\) の場合： - \(g = 6\): 倍数は \(\{6, 12, 30\}\) → \(6 \times 3 = 18\) - \(g = 15\): 倍数は \(\{15, 30\}\) → \(15 \times 2 = 30\) - \(g = 30\): 倍数は \(\{30\}\) → \(30 \times 1 = 30\)

答えは \(30\) です。

アルゴリズム

1. 頻度配列の作成: \(\text{cnt}[v]\) = \(A\) の中で値が \(v\) である要素の個数、を作ります。
2. 各 \(g\) について倍数の個数を計算: \(g = 1, 2, \ldots, \max(A)\) に対し、\(g, 2g, 3g, \ldots\) と倍数を列挙しながら \(\text{cnt}\) を足し合わせ、\(g\) の倍数の総個数 \(c_g\) を得ます。
3. 答えの更新: \(g \times c_g\) の最大値を求めます。

ステップ2は「エラトステネスの篩」と同じ要領で、各 \(g\) から倍数を列挙する手法です。

計算量

\(M = \max(A)\) とします。

• 時間計算量: \(O(N + M \log M)\)
  • 頻度配列の構築に \(O(N)\)
  • 倍数の列挙は \(\sum_{g=1}^{M} \lfloor M/g \rfloor = O(M \log M)\)（調和級数）
  • \(M, N \leq 10^6\) なので十分高速です。
• 空間計算量: \(O(M)\)
  • 頻度配列 \(\text{cnt}\) のサイズ

実装のポイント

• \(A_i\) の最大値 \(M\) を先に求め、サイズ \(M+1\) の配列を確保します。\(M\) が不必要に大きいとメモリ・時間の無駄になります。

• Pythonでは入力を sys.stdin.buffer.read() でまとめて読むことで高速化しています。

• 内側のループ range(g, MAX_VAL + 1, g) がPythonの range で効率的に倍数を列挙する定番テクニックです。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。