难度: Hard
给你一个由正整数组成的数组 nums 。
数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。
[4,6,16] 的最大公约数是 2 。数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。
[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。
示例 1：
输入：nums = [6,10,3] 输出：5 解释：上图显示了所有的非空子序列与各自的最大公约数。 不同的最大公约数为 6 、10 、3 、2 和 1 。
示例 2：
输入：nums = [5,15,40,5,6] 输出：7
提示：
1 <= nums.length <= 1051 <= nums[i] <= 2 * 105运行时间: 1482 ms
内存: 30.5 MB
class Solution:
def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
maxVal = max(nums)
occured = [False] * (maxVal + 1)
for num in nums:
occured[num] = True
ans = 0
for i in range(1, maxVal + 1):
subGcd = 0
for j in range(i, maxVal + 1, i):
if occured[j]:
if subGcd == 0:
subGcd = j
else:
subGcd = gcd(subGcd, j)
if subGcd == i:
ans += 1
break
return ans
这个题解采用了一种遍历所有可能的最大公约数的方法来解决问题。首先，它找到数组中的最大值 maxVal，因为任何子序列的最大公约数不可能大于数组中的最大值。接着，创建一个布尔数组 occured 来标记哪些数字在原数组中出现过。然后，对于每一个可能的最大公约数 i（从1到maxVal），它通过遍历所有 i 的倍数来检查这些倍数是否出现在原数组中，并计算这些倍数的最大公约数。如果在某个点最大公约数降到了 i，就意味着存在一个子序列的最大公约数正好是 i。通过这种方法，可以找出所有可能的最大公约数，最后返回这些不同最大公约数的数量。
时间复杂度: O(maxVal log maxVal)
空间复杂度: O(maxVal)
class Solution:
def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
maxVal = max(nums) # 找到数列中的最大值
occured = [False] * (maxVal + 1) # 初始化数组，记录每个数是否出现
for num in nums:
occured[num] = True # 标记出现过的数字
ans = 0
for i in range(1, maxVal + 1): # 对于每个可能的GCD i
subGcd = 0 # 初始化子序列GCD
for j in range(i, maxVal + 1, i): # 遍历i的倍数
if occured[j]: # 如果这个倍数出现过
if subGcd == 0:
subGcd = j # 初始化subGcd为j
else:
subGcd = gcd(subGcd, j) # 更新GCD
if subGcd == i: # 如果GCD降到了i
ans += 1 # 找到一个新的GCD
break
return ans # 返回不同GCD的数量
从1到maxVal进行遍历是因为最大公约数的定义决定了其值不能超过序列中的最大值。遍历这个范围确保不遗漏任何可能的GCD。但是，确实可以通过预处理和优化来减少不必要的遍历。例如，如果某个数字在数组中未出现，那么这个数字的任何倍数都无需作为GCD进行考虑，因为没有子序列的所有元素都是这个倍数。另一种优化是在发现当前GCD与正在探索的i相等时立即终止内层循环，因为更大的倍数不会产生更小的GCD。
当subGcd等于i时中断循环的逻辑是基于最大公约数的性质。在遍历i的所有倍数时，如果在某个点计算的subGcd降到了i，这意味着存在一个子序列，其元素的公约数恰好等于i，且不能有更大的值作为其GCD（因为我们是从i的倍数开始的）。这时，继续检查更高的倍数将不会再降低subGcd的值，因此可以确认i作为一个有效的GCD，并中断循环以避免不必要的计算。
先检查`if occured[j]`是为了确保只计算出现在原数组中的数字的GCD，这是因为只有这些数字才能构成有效的子序列。如果直接计算所有i的倍数的GCD，将包括许多原数组中不存在的数，这不仅增加了计算负担，还可能导致错误的结果（因为实际不存在的数不能构成任何子序列）。因此，这种先检查再计算的方法能够有效地减少计算次数和避免错误，提高算法效率和准确性。