从 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 按降序排序

  • occurrence := 一个大小为 A[0] 并填充为 0 的数组

  • 对于 i 从 0 到 n，执行：

    • occurrence[A[i]] := occurrence[A[i]] + 1

  • size := n 的平方根的整数部分

  • res := 一个大小与 A 相同并填充为 0 的数组

  • l := 0

  • 对于 i 从 0 到 n，执行：

    • 如果 occurrence[A[i]] > 0，则：

      • res[l] := A[i]

      • occurrence[res[l]] := occurrence[res[l]] - 1

      • l := l + 1

      • 对于 j 从 0 到 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]

更新于：2020年8月25日

156 次浏览

开启你的职业生涯

完成课程获得认证

开始
广告