โปรแกรมหาจำนวนองค์ประกอบติดกันในเมทริกซ์ที่ GCD > 1 ใน Python

กำหนดเมทริกซ์ขนาด n แถว m คอลัมน์ ต้องการหาจำนวนสูงสุดขององค์ประกอบที่ติดกัน (horizontally หรือ vertically) ที่มี GCD (ตัวหารร่วมมาก) มากกว่า 1

ตัวอย่าง

เมทริกซ์:

m = 4, n = 3 → เอาต์พุต: 3

คอลัมน์ที่ 4: 12, 6, 10 มี GCD = 2 มี 3 องค์ประกอบติดกัน

วิธีแก้ปัญหา

1. สร้าง 3D array mat ขนาด m × n × n เก็บ GCD ของแถว i ถึง j ในคอลัมน์ k
2. วนลูปทุกคู่แถว (i, j) คำนวณ GCD สะสมในแต่ละคอลัมน์
3. ติดตามความยาวลำดับที่ GCD > 1 ติดต่อกัน
4. อัปเดตค่าสูงสุด

ตัวอย่างโค้ด

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]]))

อินพุต / เอาต์พุต

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

หมายเหตุ: โค้ดต้นฉบับมีบั๊กในการสร้าง 3D list (ใช้ [[[0]*m]*n]*n ซึ่งสร้าง reference เดียวกัน) โค้ดข้างบนแก้ไขแล้ว