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

假设我们有一个具有正值的数组 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个数字。

要解决这个问题，我们将遵循以下步骤−

T := nums的最大值+1
nums：一个新的包含nums所有不同数字的集合
Ans：= 0
对于x in range 1到T-1，执行以下步骤
- g : = 0
- 对于y in range x to 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))