在 Python 中查找不同子序列 GCD 数量的程序

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个具有正值的数组 nums。我们必须在 nums 的所有非空子序列中找到不同 GCD 的数量。正如我们所知，数字序列的 GCD 是将序列中所有数字均分的最大值。

因此，如果输入类似于 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个数字。

示例

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

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

以上是 在 Python 中查找不同子序列 GCD 数量的程序 的全部内容， 来源链接： utcz.com/z/353538.html

回到顶部