在 Python 中寻找矩阵中 GCD 大于 1 的连续元素的数量

假设我们有一个包含 n 行和 m 列的矩阵。我们需要找出矩阵中 GCD 大于 1 的连续元素的最大数量。连续的元素可以水平或垂直地存在于矩阵中。

例如，如果输入如下所示，其中 m=4，n=3，则输出将为 3。

3	7	9	12
5	9	4	6
7	8	5	10

给定矩阵的第四列为 12、6、10。该列元素的 GCD 为 2。由于有三个元素，答案为 3。

为了解决这个问题，我们将遵循以下步骤 –

• mat := dimensions 为 m x n x n 的新 3D 列表
• res := 0
  • 对于 i 在 0 到 n 范围内，执行以下操作
    • 对于 j 在 i 到 n 的范围内，执行以下操作
    • gcd_temp := 0
    • x := 0
    • 对于 k 在 0 到 m 范围内，执行以下操作
      • 如果 i 与 j 相同，则
      • mat[i, j, k] := input_list[i, k]
      • 否则，
      • mat[i, j, k] = 元素(mat[i, j-1, k], input_list[j, k]) 的 GCD
      • gcd_temp = 元素(gcd_temp, mat[i, j, k]) 的 GCD
      • 如果 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 的最大值
• 返回 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