用 Python 编写程序来查找不同子序列 GCD 的数量

pythonserver side programmingprogramming更新于 2025/12/14 5:32:17

假设我们有一个包含正值的数组 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 := 一个新的包含所有不同数字的集合
ans := 0
对于范围从 1 到 T - 1 的 x，执行
- g := 0
- 对于范围从 x 到 T - 1 的 y，在每个步骤中用 x 更新，执行
  - 如果 y 在数字中，则
    - 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))