পাইথনে 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 কে ডিসেন্ডিং অর্ডারে সর্ট করুন
• occurrence := A[0]+1 আকারের অ্যারে 0 দিয়ে ভরুন
• প্রতিটি A[i]-র জন্য occurrence[A[i]] বাড়ান
• size := int(sqrt(n))
• res := A-এর আকারের অ্যারে 0 দিয়ে ভরুন
• l := 0
• for i in range(n):
  • যদি occurrence[A[i]] > 0 হয়:
    • res[l] := A[i]
    • occurrence[res[l]] কমানো
    • l := l + 1
    • for j in range(l):
      • যদি i != j হয়:
        • g := gcd(A[i], res[j])
        • occurrence[g] := occurrence[g] - 2
• res[0:size] রিটার্ন করুন

উদাহরণ

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]