Chương trình tìm số phần tử liên tiếp trong ma trận có GCD > 1 trong Python

Cho ma trận n hàng, m cột. Tìm số lượng phần tử liên tiếp lớn nhất (theo hàng hoặc cột) có GCD (ước chung lớn nhất) > 1.

Ví dụ

Ma trận 3×4:

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

Thuật toán (Dynamic Programming trên cột)

Duyệt tất cả cặp hàng (i, j) với i ≤ j. Với mỗi cột k, tính GCD của các phần tử từ hàng i đến j ở cột k. Theo dõi độ dài đoạn liên tiếp cột có GCD > 1.

1. Tạo mảng 3D mat[i][j][k] = GCD(cột k từ hàng i đến j)
2. Với mỗi cặp (i,j), duyệt cột k:
   • Cập nhật GCD tích lũy gcd_temp
   • Nếu > 1: tăng độ dài đoạn hiện tại
   • Nếu ≤ 1: cập nhật kết quả, reset đoạn mới nếu phần tử hiện tại > 1
3. Trả về độ dài lớn nhất

Mã nguồn

from math import gcd

def solve(n, m, input_list):
    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]]))  # Output: 3

Lưu ý về mã nguồn gốc

Code gốc có lỗi khởi tạo mảng 3D: mat = [[[0] *m] *n] *n tạo tham chiếu chung (shallow copy). Đã sửa trong phiên bản trên bằng list comprehension.

Độ phức tạp: O(n² × m) thời gian, O(n² × m) không gian. Có thể tối ưu không gian xuống O(n × m) bằng cách tính GCD trực tiếp không lưu mat 3D.