Python程序：查找不同子序列的最大公约数

假设我们有一个包含正数的数组 nums。我们需要找到 nums 所有非空子序列中不同最大公约数的数量。众所周知，一个数字序列的最大公约数是指能整除该序列中所有数字的最大值。

例如，如果输入为 nums = [4,6,18]，则输出将为 4，因为 gcd([4]) = 4，gcd([6]) = 6，gcd([18]) = 18，gcd([4,6]) = 2，gcd([4,18]) = 2，gcd([6,18]) = 6，gcd([4,6,18]) = 2，所以所有数字为 [4,6,18,2]，共有 4 个数字。

为了解决这个问题，我们将遵循以下步骤：

  • T := nums 中最大值的加 1

  • nums := 包含 nums 所有不同数字的新集合

  • ans := 0

  • 对于 x 从 1 到 T - 1，执行以下操作：

    • g := 0

    • 对于 y 从 x 到 T - 1，每次递增 x，执行以下操作：

      • 如果 y 在 nums 中，则

        • g := gcd(g, y)

      • 如果 g 等于 x，则

        • 退出循环

    • 如果 g 等于 x，则

      • ans := ans + 1

  • 返回 ans

示例

让我们看看下面的实现以更好地理解

from math import gcd
def solve(nums):
   T = max(nums) + 1
   nums = set(nums)
   ans = 0

   for x in range(1, T):
      g = 0
      for y in range(x, T, x):
         if y in nums:
            g = gcd(g, y)
         if g == x:
            break

      if g == x:
         ans += 1

   return ans

nums = [4,6,18]
print(solve(nums))

输入

[4,6,18]

输出

4

更新于: 2021年10月8日

140 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告