Pythonで数列の部分列から得られる異なるGCDの個数を求めるプログラム

問題概要

正の整数からなる配列 nums が与えられたとき、nums のすべての空でない部分列についてGCD(最大公約数)を計算し、その結果として現れる「異なるGCDの値」が何種類あるかを求めます。ここで、数列のGCDとは、その数列に含まれるすべての数を余りなく割り切ることができる最大の整数のことです。

入力例と出力例

たとえば、入力が nums = [4, 6, 18] の場合、出力は 4 になります。各部分列のGCDを列挙すると次のようになります。

• gcd([4]) = 4
• gcd([6]) = 6
• gcd([18]) = 18
• gcd([4, 6]) = 2
• gcd([4, 18]) = 2
• gcd([6, 18]) = 6
• gcd([4, 6, 18]) = 2

これらをまとめると、現れる値は {2, 4, 6, 18} の4種類であるため、答えは 4 となります。

解法のアプローチ

すべての部分列を実際に生成してGCDを計算するのは非効率です。部分列の総数は要素数に対して指数的に増えるためです。そこで、エラトステネスの篩に似た「約数・倍数ごとにまとめて調べる」手法を使います。

各候補値 x(1 以上 配列の最大値以下)について、「x の倍数のうち配列に存在する要素」だけを集めてGCDを計算します。もし得られたGCDがちょうど x になれば、x は何らかの部分列のGCDとして実現できる値だということになります。

アルゴリズムの手順

1. T を「配列の最大値 + 1」とします。
2. 存在判定を高速化するため、nums を集合(set)に変換します。
3. 答えを格納する変数 ans を 0 で初期化します。
4. x を 1 から T-1 まで順に試します。
   • g を 0 で初期化します。
   • y を x, 2x, 3x, … と x 刻みで走査し、y が nums に存在すれば g = gcd(g, y) で更新します。
   • 途中で g が x になったら、それ以上調べても結果は変わらないためループを抜けます。
5. 内側の処理の後、g が x と一致していれば ans を 1 増やします。
6. 最後に ans を返します。

Pythonでの実装例

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

from math import gcd

def solve(nums):
    T = max(nums) + 1
    nums = set(nums)
    ans = 0

    for x in range(1, T):
        g = 0
        for y in range(x, T, x):
            if y in nums:
                g = gcd(g, y)
            if g == x:
                break

        if g == x:
            ans += 1

    return ans

nums = [4, 6, 18]
print(solve(nums))

実行結果

入力:

[4, 6, 18]

出力:

4

計算量について

外側のループは O(T) 回、内側のループは合計で T/1 + T/2 + … + T/(T-1) ≒ O(T log T) 回程度しか実行されないため、全体の計算量はほぼ O(T log T) です。部分列を全列挙する指数時間のアプローチと比べると、非常に効率的であることがわかります。

まとめ

本記事では、配列のすべての空でない部分列から得られる異なるGCDの個数をPythonで求める方法を紹介しました。ポイントは「候補となる値 x の倍数だけを対象にGCDを更新する」という篩のような発想です。この工夫により、全部分列を列挙することなく効率的に答えを求められます。