Tìm các số gốc từ gcd () mọi cặp trong Python

Giả sử chúng ta có một mảng A trong đó GCD của mọi cặp phần tử có thể có của một mảng khác được cung cấp, chúng ta phải tìm các số ban đầu được sử dụng để tính mảng GCD đã cho.

Vì vậy, nếu đầu vào là A =[6, 1, 1, 13], thì đầu ra sẽ là [13, 6] vì gcd (13, 13) là 13, gcd (13, 6) là 1, gcd ( 6, 13) là 1, gcd (6, 6) là 6

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của A

• sắp xếp mảng A theo thứ tự giảm dần

• xuất hiện:=một mảng có kích thước A [0] và điền bằng 0

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • xuất hiện [A [i]]:=xuất hiện [A [i]] + 1

• size:=số nguyên căn bậc hai của n

• res:=một mảng có kích thước giống như kích thước của A và điền bằng 0

• l:=0

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • nếu sự xuất hiện [A [i]]> 0, thì

    • res [l]:=A [i]

    • xuất hiện [res [l]]:=xuất hiện [res [l]] - 1

    • l:=l + 1

    • đối với j trong phạm vi từ 0 đến l, thực hiện

      • nếu tôi không giống với j, thì

        • g:=gcd (A [i], res [j])

        • Lần xuất hiện [g]:=Lần xuất hiện [g] - 2

• trả về res [từ chỉ mục 0 đến kích thước]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

from math import sqrt, gcd
def get_actual_array(A):
   n = len(A)
   A.sort(reverse = True)
   occurrence = [0 for i in range(A[0] + 1)]
   for i in range(n):
      occurrence[A[i]] += 1
   size = int(sqrt(n))
   res = [0 for i in range(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))

Đầu vào

[6, 1, 1, 13]

Đầu ra

[13, 6]