在 Python 中通过 gcd() 查找每对元素的原始数字

pythonserver side programmingprogramming更新于 2025/10/10 22:36:17

假设我们有一个数组 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] 并用 0 填充
对于范围为 0 到 n 的 i，执行
- occurrence[A[i]] := appearance[A[i]] + 1
size := n 平方根的整数
res := 大小与 A 大小相同的数组并用 0 填充
l := 0
对于范围为 0 到 n 的 i，执行
- if appearance[A[i]] > 0，则
  - res[l] := A[i]
  - occurrence[res[l]] := appearance[res[l]] - 1
  - l := l + 1
  - 对于 j 在 0 到 l 范围内的情况，执行
    - 如果 i 与 j 不同，则
      - g := gcd(A[i], res[j])
      - occurrence[g] := appearance[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))