PythonでGCDを大きくするために必要な配列からの最小削除数を求めるアルゴリズム

N個の整数で構成されるリストが与えられ、残りの数値のGCD（最大公約数）が、元のN個すべてのGCDよりも大きくなるようにするには、最低何個の数値を取り除けばよいでしょうか。この記事では、その最小削除数を効率よく求めるアルゴリズムをPythonで解説します。

たとえば、入力が [6, 9, 15, 30] の場合、出力は 2 になります。初期のGCDは 3 ですが、6 と 9 を削除すると残りは 15 だけとなり、GCDは 15。これは 15 > 3 を満たすためです。

解法のポイント

まず配列全体のGCDを g として求め、各要素を g で割って正規化します。正規化後の配列全体のGCDは必ず 1 になります。ここで、ある素因数 p が k 個の要素を割り切れるなら、それ以外の n − k 個を削除すれば、残った要素のGCDは p 以上の値になり、元のGCDより確実に大きくなります。つまり「最も多くの要素に共通して現れる素因数」を見つけることが答えを導く鍵です。

アルゴリズムの手順

• INF := 100001 とし、0〜INFの値を持つ最小素因数（SPF）テーブルを初期化します。
• sieve() 関数を定義し、エラトステネスの篩の考え方で各数値の最小素因数を前計算します。
• calc_fact(x) 関数を定義し、SPFテーブルを使って x を素因数分解し、素因数のリストを返します。
• メイン処理では以下を行います。
  • 配列全体のGCD g を計算します。
  • 各要素を g で整数除算して正規化します。
  • 各要素を素因数分解し、重複を除いた素因数ごとに、その素因数で割り切れる要素の数をマップにカウントします。
  • n − 出現数 の最小値を答えの候補とします。
  • 候補が存在すればその値を返し、どの素因数もカウントされない（すべての要素が g と等しい）場合は -1 を返します。

計算量は、篩の前計算に O(INF log log INF)、素因数分解と集計は要素数と値の大きさに対してほぼ線形のオーダーで済むため、比較的大きな入力にも対応できるのが特徴です。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

from math import gcd as __gcd
INF = 100001
spf = [i for i in range(INF)]
def sieve():
    for i in range(4, INF, 2):
        spf[i] = 2
    for i in range(3, INF):
        if i**2 > INF:
            break
        if (spf[i] == i):
            for j in range(2 * i, INF, i):
                if (spf[j] == j):
                    spf[j] = i
def calc_fact(x):
    ret = []
    while (x != 1):
        ret.append(spf[x])
        x = x // spf[x]
    return ret
def minRemove(a, n):
    g = 0
    for i in range(n):
        g = __gcd(a[i], g)
    my_map = dict()
    for i in range(n):
        a[i] = a[i] // g
    for i in range(n):
        p = calc_fact(a[i])
        s = dict()
        for j in range(len(p)):
            s[p[j]] = 1
        for i in s:
            my_map[i] = my_map.get(i, 0) + 1
    minimum = 10**9
    for i in my_map:
        first = i
        second = my_map[i]
        if ((n - second) <= minimum):
            minimum = n - second
    if (minimum != 10**9):
        return minimum
    else:
        return -1
a = [6, 9, 15, 30]
n = len(a)
sieve()
print(minRemove(a, n))

入力

[6, 9, 15, 30], 4

出力

2

このように、全体のGCDで正規化したうえで素因数の出現状況を集計するだけで、余分な組み合わせ探索なしに最小削除数を求められます。GCDや素因数分解を扱う競技プログラミングの問題でも応用できるテクニックなので、ぜひ覚えておきましょう。