Tìm số gốc từ mảng GCD của mọi cặp trong Python

Cho mảng A chứa GCD của mọi cặp phần tử của một mảng khác, tìm mảng số gốc đã dùng để tính mảng GCD này.

Ví dụ: A = [6, 1, 1, 13] → Kết quả: [13, 6] vì gcd(13,13)=13, gcd(13,6)=1, gcd(6,13)=1, gcd(6,6)=6.

Thuật toán

1. Sắp xếp A giảm dần.
2. Đếm tần suất xuất hiện của mỗi giá trị.
3. Kích thước mảng gốc = √(độ dài A).
4. Duyệt A, nếu phần tử còn tần suất > 0: thêm vào kết quả, giảm tần suất, và trừ 2 lần tần suất của GCD với các phần tử đã chọn.
5. Trả về các phần tử đầu tiên của kết quả.

Ví dụ code

from math import sqrt, gcd

def get_actual_array(A):
    n = len(A)
    A.sort(reverse=True)
    occurrence = [0] * (A[0] + 1)
    for i in range(n):
        occurrence[A[i]] += 1
    size = int(sqrt(n))
    res = [0] * len(A)
    l = 0
    for i in range(n):
        if occurrence[A[i]] > 0:
            res[l] = A[i]
            occurrence[res[l]] -= 1
            l += 1
            for j in range(l):
                if i != j:
                    g = gcd(A[i], res[j])
                    occurrence[g] -= 2
    return res[:size]

A = [6, 1, 1, 13]
print(get_actual_array(A))

Input

[6, 1, 1, 13]

Output

[13, 6]