概要

\(N\) 個の宝石から2個以上を選び、GCD（最大公約数）を最大化し、さらにそのGCDを達成する最小個数 \(K\) を求めて \(N - K\) を出力する問題。結論として \(K = 2\) が常に成り立ち、答えは \(N - 2\) となる。

考察

重要な気づき 1: 最大GCD \(G\) の求め方

ある値 \(g\) が2個以上の宝石の集合のGCDとして実現可能であるためには、少なくとも \(g\) の倍数が配列中に2個以上存在する必要があります。

逆に、\(g\) の倍数が2個以上あれば、その中から2つ選べば GCD ≥ \(g\) が保証されます。

したがって、\(G\) = 「\(g\) の倍数が配列中に2個以上存在する」ような最大の \(g\) として求められます。

重要な気づき 2: \(K = 2\) が常に成り立つ

\(G\) は上記の最大値なので、\(G\) の倍数が配列中に2個以上あります。この中から任意の2つを選ぶと、それらのGCDを \(d\) とすると：

• 両方とも \(G\) の倍数なので \(d \geq G\)
• もし \(d > G\) なら、\(d\) の倍数も配列中に2個以上存在することになり、\(G\) の最大性に矛盾

よって \(d = G\) が必ず成り立ち、たった2個選ぶだけでGCD \(= G\) を達成できます。

結論: \(K = 2\) であり、答えは常に \(N - 2\)

素朴な方法ではなぜ問題になるか

各 \(g\) について愚直に配列を走査して倍数の個数を数えると \(O(N \cdot \max(A))\) で TLE の恐れがあります。エラトステネスの篩のようなテクニックで効率化します。

アルゴリズム

1. 配列 \(A\) の各値の出現回数 \(\text{cnt}[v]\) を集計する。
2. 篩のように、各 \(g = 1, 2, \ldots, \max(A)\) について、\(g, 2g, 3g, \ldots\) の出現回数を合計し、\(\text{divisor\_count}[g]\) =「\(g\) の倍数の個数」を求める。
3. \(g\) を大きい順に見て、\(\text{divisor\_count}[g] \geq 2\) となる最初の \(g\) が \(G\)。
4. 上の考察より \(K = 2\) なので、\(N - 2\) を出力する。

具体例: \(A = [6, 10, 15]\)（\(N = 3\)）

• \(\text{divisor\_count}[5] = 2\)（10と15）, \(\text{divisor\_count}[6] = 1\), \(\text{divisor\_count}[10] = 1\), …
• 最大の \(g\) で count ≥ 2 は \(g = 5\)。\(G = 5\)。
• \(\gcd(10, 15) = 5 = G\)。\(K = 2\)。答え: \(3 - 2 = 1\)。

計算量

• 時間計算量: \(O(M \log M)\)（\(M = \max(A_i)\)、調和級数 \(\sum_{g=1}^{M} \lfloor M/g \rfloor = O(M \log M)\)）
• 空間計算量: \(O(M)\)

実装のポイント

• 篩の計算は \(g = 1\) から \(\max(A)\) まで、各 \(g\) について \(g\) の倍数を走査する。合計ループ回数は調和級数 \(O(M \log M)\) で十分高速。

• \(G\) の最大性から \(K = 2\) が自動的に保証されるため、最小部分集合を探索する処理は不要。

• 問題の本質は「\(K = 2\) が常に成り立つ」ことに気づけるかどうかにある。

  ソースコード

import sys

def solve():
    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) + 1
    
    # Count occurrences of each value
    cnt = [0] * MAX_VAL
    for a in A:
        cnt[a] += 1
    
    # For each possible GCD value g (from large to small),
    # count how many elements in A are divisible by g.
    # If count >= 2, then g is achievable as a GCD of some subset.
    # But we need the actual GCD of those elements to be exactly g, not a multiple of g.
    # 
    # Wait, actually if we pick elements divisible by g, their GCD is a multiple of g.
    # We need to find the maximum g such that there exist >= 2 elements whose GCD is exactly g.
    #
    # Better approach: For each g from large to small, count how many A_i are divisible by g.
    # If that count >= 2, then we can pick a subset of those elements. The GCD of all elements
    # divisible by g is some multiple of g, say g' >= g. But g' would have been considered
    # before g (since we go from large to small). So if g' > g, then g' already has count >= 2
    # and we would have found g' first.
    #
    # Actually, we need to be more careful. Let me think again.
    #
    # We want the maximum G such that there exist >= 2 elements whose GCD equals G.
    # 
    # For each g from MAX_VAL-1 down to 1:
    #   Collect all A_i divisible by g. Let there be c(g) such elements.
    #   If c(g) >= 2, compute the GCD of all those elements divided by g.
    #   If that GCD is 1, then the GCD of those elements is exactly g.
    #   But we want subset GCD = g, and we want minimum subset size.
    #   Actually, if c(g) >= 2, we can always find a subset with GCD exactly g IF
    #   there's no larger g' that all of them share. But some subset of them might have GCD = g.
    #
    # Simpler correct approach:
    # For each g from large to small, count c(g) = number of A_i divisible by g.
    # If c(g) >= 2, then the GCD of ANY subset of size >= 2 from those elements is a multiple of g.
    # The GCD of ALL c(g) elements is the GCD of (A_i/g for A_i divisible by g) times g.
    # If that overall GCD equals g, then picking all of them gives GCD = g, but we want min subset.
    # 
    # Key insight: G = max g such that c(g) >= 2.
    # Because if c(g) >= 2, pick any 2 elements divisible by g. Their GCD is >= g.
    # But for any g' > g, c(g') < 2, so no pair has GCD > g. Hence G = g.
    # And K = minimum subset size with GCD = g among elements divisible by g.
    # Since we want GCD exactly g, we need GCD of chosen subset = g.
    # The minimum such subset: we need to find minimum number of elements (among those divisible by g)
    # whose GCD (after dividing by g) is 1.
    
    # Find G: largest g with c(g) >= 2
    # Compute c(g) for all g using sieve-like approach
    
    divisor_count = [0] * MAX_VAL
    for g in range(1, MAX_VAL):
        for multiple in range(g, MAX_VAL, g):
            divisor_count[g] += cnt[multiple]
    
    G = 1
    for g in range(MAX_VAL - 1, 0, -1):
        if divisor_count[g] >= 2:
            G = g
            break
    
    # Now find K: minimum subset size among elements divisible by G with GCD = G
    # Collect elements divisible by G, divide by G, find min subset with GCD 1
    elements = []
    for a in A:
        if a % G == 0:
            elements.append(a // G)
    
    # We need minimum subset of `elements` with GCD = 1.
    # Since overall GCD of all elements must be 1 (otherwise G wouldn't be the max),
    # and we want minimum subset size.
    # Greedy: start with first element, keep taking GCD with next elements, stop when GCD = 1.
    # But greedy order matters. With N up to 10^6, trying all pairs: if any pair has GCD 1, answer is 2.
    # Otherwise answer is at most small. But finding exact minimum is hard in general.
    # However, K=2 if any pair among them has GCD=1 (i.e., coprime after dividing by G).
    # Since G is maximum, there's no g > G with 2+ multiples, so K=2 always.
    # Because if all pairs had GCD > 1 after dividing by G, then... actually that's possible.
    # But K is always 2 because G is the max g with >=2 multiples. Pick any two such elements: their GCD is exactly G.
    # Wait, their GCD could be a multiple of G. But then that multiple would have count >= 2, contradicting maximality of G.
    
    K = 2
    print(N - K)

solve()

---

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