PythonでGCDが1より大きい行列の連続要素の最大数を求めるプログラム

n行・m列の行列が与えられたとします。この中から、要素のGCD（最大公約数）が1より大きくなるような「連続する要素」の最大数を求めるのが今回の課題です。連続する要素は、行方向（水平）・列方向（垂直）のどちらに並んでいても構いません。

例として、次のような入力を考えてみましょう。

m = 4、n = 3 のとき、出力は 3 になります。

その理由は、行列の第4列が「12, 6, 10」と並んでおり、これら3つの要素のGCDが 2（1より大きい）になるためです。該当する要素が3つあるので、答えは3となります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• mat := サイズ m × n × n の新しい3次元リストを用意する
• res := 0（最終結果を保持する変数）
• i を 0 から n-1 まで繰り返す
  • j を i から n-1 まで繰り返す
    • gcd_temp := 0、x := 0 で初期化する
    • k を 0 から m-1 まで繰り返す
      • i と j が等しい場合：mat[i][j][k] := input_list[i][k]
      • それ以外の場合：mat[i][j][k] := gcd(mat[i][j-1][k], input_list[j][k])
      • gcd_temp := gcd(gcd_temp, mat[i][j][k])
      • gcd_temp > 1 の場合：x := x + (j − i + 1)
      • それ以外の場合：res := max(res, x) とし、さらに mat[i][j][k] > 1 であれば gcd_temp := mat[i][j][k]、x := j − i + 1 とする
    • 内側のループを抜けたら res := max(res, x)
• res を返す

実装例

理解を深めるために、実際の実装例を見てみましょう。

from math import gcd

def solve(n, m, input_list):
    # mat[i][j][k] := 行i〜行jのk列目の要素のGCD
    mat = [[[0] * m for _ in range(n)] for _ in range(n)]
    res = 0
    for i in range(n):
        for j in range(i, n):
            gcd_temp = 0
            x = 0
            for k in range(m):
                if i == j:
                    mat[i][j][k] = input_list[i][k]
                else:
                    mat[i][j][k] = gcd(mat[i][j-1][k], input_list[j][k])
                gcd_temp = gcd(gcd_temp, mat[i][j][k])
                if gcd_temp > 1:
                    x += j - i + 1
                else:
                    res = max(res, x)
                    if mat[i][j][k] > 1:
                        gcd_temp = mat[i][j][k]
                        x = j - i + 1
            res = max(res, x)
    return res

print(solve(3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]))

入力

3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]

出力

3

アルゴリズムのポイント

このアルゴリズムの鍵となるのは、行のペア (i, j) ごとに「行i〜行jの区間における列ごとのGCD」を累積的に再利用しながら計算している点です。mat[i][j][k] は「行iから行jまでのk列目の要素のGCD」を表し、ひとつ前の状態 mat[i][j-1][k] とのGCDを取るだけで更新できるため、無駄な再計算を避けられます。

また、gcd_temp が1より大きな値を保っている間は連続性が継続しているとみなし、GCDが1になった時点で走査をリセットします。これは「一度GCDが1になれば、そこに要素を追加してもGCDは1のまま」という性質を利用したものです。単一行（i = j）の走査では行内の水平方向の連続要素が、複数行にまたがる走査では列方向の連続要素が評価されます。全体の計算量は O(n² × m) 程度に収まります。