Pythonでgcdが1より大きい行列の連続する要素の数を見つけるプログラム

n行m列を含む行列が与えられたとします。要素のgcdが1より大きい、マトリックス内の連続する要素の最大数を見つける必要があります。連続する要素は、マトリックス内で水平または垂直に配置できます。

したがって、入力が次のような場合

およびm=4、n =3;その場合、出力は3になります。

与えられた行列の4番目の列は12、6、10です。この列の要素のgcdは2です。3つの要素があるので、答えは3です。

これを解決するには、次の手順に従います-

• mat：=寸法の新しい3Dリストm x n x n
• res：=0
  • 0からnの範囲のiについては、
    • iからnの範囲のjについては、
      • gcd_temp：=0
      • x：=0
      • 0からmの範囲のkについては、
        • 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：=resの最大値、x
          • mat [i、j、k]> 1の場合、
            • gcd_temp：=mat [i、j、k]
            • x：=j-i + 1
  • res：=resの最大値、x
• return res

例

理解を深めるために、次の実装を見てみましょう-

from math import gcd
def solve(n, m, input_list):
   mat = [[[0] *m] *n] *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