파이썬에서 gcd가 1보다 큰 행렬의 연속 요소 수를 찾는 프로그램

n개의 행과 m개의 열이 포함된 행렬이 있다고 가정합니다. 요소의 gcd가 1보다 큰 행렬에서 연속 요소의 가장 큰 수를 찾아야 합니다. 연속 요소는 행렬에서 가로 또는 세로로 놓일 수 있습니다.

따라서 입력이 다음과 같으면

및 m =4, n =3; 그러면 출력은 3이 됩니다.

주어진 행렬의 네 번째 열은 12, 6, 10입니다. 이 열의 요소의 gcd는 2입니다. 요소가 3개 있으므로 답은 3입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• mat :=m x n x n 차원의 새로운 3D 목록
• res :=0
  • 0에서 n 사이의 i에 대해
    • i에서 n 사이의 j에 대해 다음을 수행합니다.
      • gcd_temp :=0
      • x :=0
      • 0~m 범위의 k에 대해
        • i가 j와 같으면
          • 매트[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 :=매트[i, j, k]
            • x :=j - i + 1
  • res :=최대 res, x
• 반환 결과

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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