在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]