Tìm ước số chung của tất cả trừ một phần tử trong mảng Python

Cho mảng số, tìm số B là ước của tất cả phần tử trừ đúng một phần tử. GCD của toàn mảng không phải 1.

Ví dụ: [8, 16, 4, 24] → 8 (ước của 8,16,24 nhưng không phải 4).

Thuật toán (prefix/suffix GCD)

• Tính mảng prefix: GCD tích lũy từ trái
• Tính mảng suffix: GCD tích lũy từ phải
• Với mỗi vị trí i, GCD của phần còn lại = gcd(prefix[i-1], suffix[i+1])
• Nếu array[i] % cur != 0 → trả về cur

Ví dụ mã Python

from math import gcd
def getDivisor(array):
    n = len(array)
    if n == 1:
        return array[0] + 1
    prefix = [0] * n
    suffix = [0] * n
    prefix[0] = array[0]
    for i in range(1, n):
        prefix[i] = gcd(array[i], prefix[i-1])
    suffix[n-1] = array[n-1]
    for i in range(n-2, -1, -1):
        suffix[i] = gcd(suffix[i+1], array[i])
    for i in range(n):
        if i == 0:
            cur = suffix[1]
        elif i == n-1:
            cur = prefix[n-2]
        else:
            cur = gcd(prefix[i-1], suffix[i+1])
        if array[i] % cur != 0:
            return cur
    return 0

array = [8, 16, 4, 24]
print(getDivisor(array))

Đầu vào

[8, 16, 4, 24]

Đầu ra

8