পাইথনে প্রতিটি জোড়া gcd() থেকে আসল সংখ্যা খুঁজুন

ধরুন আমাদের একটি অ্যারে 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[0] আকারের একটি অ্যারে এবং 0

  দিয়ে পূরণ করুন

• 0 থেকে n রেঞ্জের জন্য, করুন

  • সংঘটন[A[i]] :=সংঘটন[A[i]] + 1

• আকার :=n

  এর বর্গমূলের পূর্ণসংখ্যা

• res :=A এর আকারের সমান আকারের একটি অ্যারে এবং 0

  দিয়ে পূরণ করুন

• l :=0

• 0 থেকে n রেঞ্জের জন্য, করুন

  • যদি সংঘটিত হয় [A[i]]> 0, তারপর

    • res[l] :=A[i]

    • সংঘটন[পুনরায়[l]] :=সংঘটিত [পুনরায়[l]] - 1

    • l :=l + 1

    • 0 থেকে l রেঞ্জে j এর জন্য, করুন

      • যদি আমি j এর মতো না হয়, তাহলে

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

        • সংঘটিত [g] :=সংঘটন [g] - 2

• রিটার্ন রিটার্ন [সূচক 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]