在 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
热门推荐
10 财运虎年祝福语简短语
11 单亲爸爸春节祝福语简短
12 狗狗上厕所训练
13 植物种植祝福语简短
14 翻译考试祝福语朋友简短
15 个人周年庆简短祝福语
16 狗狗怎么训练
17 分别祝福语简短搞笑英文
18 生日广州男生祝福语简短