Hard

题目描述

给你一个由正整数组成的数组 nums。

数字序列的 GCD 定义为能够被序列中所有数字整除的最大正整数。

  • 例如，序列 [4,6,16] 的 GCD 为 2。

数组的 子序列 是通过删除数组中的某些元素（可能不删除）而形成的序列。

  • 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

返回数组 nums 所有 非空 子序列的不同 GCD 的数量。

示例 1：

输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与它们的 GCD。
不同的 GCD 为 6、10、3、2 和 1。

示例 2：

输入：nums = [5,15,40,5,6]
输出：7

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 2 * 10^5

解题思路

解题思路

这道题需要计算所有非空子序列的不同GCD数量。直接枚举所有子序列会超时，需要转换思路。

核心观察：

  1. 对于一个给定的数值 g，如果存在某个子序列的GCD为 g，那么这个子序列中的所有元素都必须是 g 的倍数
  2. 如果数组中存在 g 的倍数，我们可以检查所有 g 的倍数组成的子序列，看它们的GCD是否恰好为 g

算法步骤：

  1. 首先统计数组中每个数字的出现情况，并记录最大值
  2. 对于每个可能的GCD值 g（从1到最大值），检查是否存在GCD为 g 的子序列：
    • 找出数组中所有 g 的倍数
    • 计算这些倍数的GCD
    • 如果GCD恰好等于 g，则 g 是一个有效的子序列GCD

优化要点：

  • 使用哈希表记录数字的存在性，避免重复计算
  • 只枚举到数组中的最大值即可
  • 利用GCD的性质进行剪枝

这种方法的时间复杂度为 O(max_val * log(max_val))，其中 max_val 是数组中的最大值。

代码实现

class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        
        int result = 0;
        
        for (int g = 1; g <= maxVal; g++) {
            int currentGCD = 0;
            
            for (int multiple = g; multiple <= maxVal; multiple += g) {
                if (numSet.count(multiple)) {
                    if (currentGCD == 0) {
                        currentGCD = multiple;
                    } else {
                        currentGCD = __gcd(currentGCD, multiple);
                    }
                    
                    if (currentGCD == g) {
                        result++;
                        break;
                    }
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        from math import gcd
        
        num_set = set(nums)
        max_val = max(nums)
        
        result = 0
        
        for g in range(1, max_val + 1):
            current_gcd = 0
            
            for multiple in range(g, max_val + 1, g):
                if multiple in num_set:
                    if current_gcd == 0:
                        current_gcd = multiple
                    else:
                        current_gcd = gcd(current_gcd, multiple)
                    
                    if current_gcd == g:
                        result += 1
                        break
        
        return result

public class Solution {
    public int CountDifferentSubsequenceGCDs(int[] nums) {
        HashSet<int> numSet = new HashSet<int>(nums);
        int maxVal = nums.Max();
        
        int result = 0;
        
        for (int g = 1; g <= maxVal; g++) {
            int currentGCD = 0;
            
            for (int multiple = g; multiple <= maxVal; multiple += g) {
                if (numSet.Contains(multiple)) {
                    if (currentGCD == 0) {
                        currentGCD = multiple;
                    } else {
                        currentGCD = GCD(currentGCD, multiple);
                    }
                    
                    if (currentGCD == g) {
                        result++;
                        break;
                    }
                }
            }
        }
        
        return result;
    }
    
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var countDifferentSubsequenceGCDs = function(nums) {
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    
    const max = Math.max(...nums);
    const exists = new Array(max + 1).fill(false);
    
    for (const num of nums) {
        exists[num] = true;
    }
    
    let count = 0;
    
    for (let i = 1; i <= max; i++) {
        let currentGCD = 0;
        
        for (let j = i; j <= max; j += i) {
            if (exists[j]) {
                if (currentGCD === 0) {
                    currentGCD = j;
                } else {
                    currentGCD = gcd(currentGCD, j);
                }
                
                if (currentGCD === i) {
                    count++;
                    break;
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(max_val × log(max_val))
空间复杂度O(n)

说明：

  • 时间复杂度：外层循环遍历1到max_val，内层循环枚举倍数，GCD计算的复杂度为O(log(max_val))
  • 空间复杂度：主要用于存储数字的哈希表，大小为O(n)

相关题目