在Python中每对从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进行排序

• 出现：=大小为A [0]并填充0的数组

• 对于0到n范围内的i，执行

• 发生[A [i]]：=发生[A [i]] + 1

• size：= n的平方根的整数

• res：=一个与A大小相同的数组，并用0填充

• l：= 0

• 对于0到n范围内的i，执行

• res [l]：= A [i]

• 事件[res [l]]：=事件[res [l]]-1

• l：= l + 1

• 对于j在0到l范围内，执行

• g：= gcd（A [i]，res [j]）

• 出现[g]：=出现[g]-2

• 如果我和j不一样

• 如果出现[A [i]]> 0，则

• 返回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]