在 Python 中查找不同子序列 GCD 数量的程序
假设我们有一个具有正值的数组nums。我们必须在nums的所有非空子序列中找到不同GCD的数量。正如我们所知，数字序列的GCD是将序列中所有数字均分的最大值。
因此，如果输入类似于nums=[4,6,18]，那么输出将为4，因为gcd([4])=4,gcd([6])=6,gcd([18])=18gcd([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