跳到主要内容

1819.序列中不同最大公约数的数目

· 阅读需 3 分钟

1、题干​

给你一个由正整数组成的数组 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 <= 105
  • 1 <= nums[i] <= 2 * 105

题目太难，看了题解才写出来。

2、思路​

所有最大公约数都处于 [1,max(nums)][1,max(nums)] 范围内，因此可以枚举该范围内的所有数字 i，判断该数字是否属于 nums 子序列的最大公约数。

具体判断时对 i 倍乘，若倍乘的数同时属于 nums 则求其最大公约数 g，g === i 则结果累加1。

3、代码​

function countDifferentSubsequenceGCDs(nums: number[]): number {
    let max = 0;
    for (const n of nums) max = n > max ? n : max;

    const set = new Array(max + 1);
    for (const n of nums) set[n] = 1;

    const gcd = (x: number, y: number) => y ? gcd(y, x % y) : x;

    let ans = 0;
    for (let i = 1; i <= max; i++) {
        if (set[i]) {
            ans++;
            continue;
        }

        let g = 0;
        for (let j = 2 * i; j <= max && g !== i; j += i) {
            if (set[j]) g = gcd(j, g);
        }

        if (g === i) ans++;
    }

    return ans;
};

4、复杂度​

  • 时间复杂度：O(n∗logn)O(n*logn)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png