ค้นหาหมายเลขเดิมจาก gcd() ทุกคู่ใน Python

สมมติว่าเรามีอาร์เรย์ A โดยที่ GCD ขององค์ประกอบที่เป็นไปได้ทุกคู่ของอาร์เรย์อื่นจะได้รับ เราต้องหาตัวเลขเดิมที่ใช้คำนวณอาร์เรย์ GCD ที่กำหนด พี>

ดังนั้น หากอินพุตเป็น A =[6, 1, 1, 13] ผลลัพธ์จะเป็น [13, 6] เนื่องจาก gcd(13, 13) คือ 13, gcd(13, 6) คือ 1, gcd( 6, 13) คือ 1, gcd(6, 6) คือ 6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A

• เรียงลำดับอาร์เรย์ A จากมากไปหาน้อย

• เกิดขึ้น :=อาร์เรย์ขนาด A[0] และเติมด้วย 0

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • เหตุการณ์[A[i]] :=เหตุการณ์[A[i]] + 1

• size :=จำนวนเต็มของรากที่สองของ n

• res :=อาร์เรย์ที่มีขนาดเท่ากับขนาด A และเติมด้วย 0

• ล :=0

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • ถ้าเกิดขึ้น[A[i]]> 0 แล้ว

    • res[l] :=A[i]

    • การเกิดขึ้น[res[l]] :=การเกิดขึ้น[res[l]] - 1

    • l :=l + 1

    • สำหรับ j ในช่วง 0 ถึง l ทำ

      • ถ้าฉันไม่เหมือน j แล้ว

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

        • เหตุการณ์[g] :=เหตุการณ์[g] - 2

• คืนค่า res[จากดัชนี 0 เป็นขนาด]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

[6, 1, 1, 13]

ผลลัพธ์

[13, 6]