在 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 英语祝福语图画大全简短