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

又到了我是傻逼环节了, 2022 年 12 月 31 日 21:08:13

题目描述

给你一个由正整数组成的数组 $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

提示:

$$
\begin{align}
&1 \le nums.length \le 10^5\\
&1 \le nums[i] \le 2 * 10^5\\
\end{align}
$$

解答

思路

这个题目实际上是一个计数类型的, 不是求最大值, 所以也用不上 DP.

数据量是 $1 \times 10^5$, 所以枚举所有的子序列并计算子序列中所有数的最大公约数显然会超时的.

这里需要转换一下思路, 不是枚举所有的子序列, 而是枚举所有可能成为最大公约数的数.

可能的公约数的范围是 $[1,\ \max(nums)]$.

对于 $\forall\ i \in [1,\ \max(nums)]$, 需要找到是否有一个子序列以它为最大公约数, 就可以将结果加 $1$.

问题是如何找到一个以 $i$ 为最大公约数的子序列呢?

我们可以枚举 $i$ 的倍数, 并设初始的 $divisor = 0$, 然后每次都更新 $divisor$, 只要最后 $divisor == i$ 为 true, 就将计数的结果加 1.

参考代码1

class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int maxVal = Arrays.stream(nums).max().getAsInt();
        boolean[] occurred = new boolean[maxVal + 1];
        for (int num : nums) {
            occurred[num] = true;
        }
        int count = 0;
        for (int i = 1; i <= maxVal; i++) {
            int divisor = 0;
            for (int j = i; j <= maxVal && divisor != i; j += i) {
                if (occurred[j]) {
                    divisor = gcd(divisor, j);
                }
            }
            if (divisor == i) {
                count++;
            }
        }
        return count;
    }

    public int gcd(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }
}

作者：stormsunshine
链接：https://leetcode.cn/problems/number-of-different-subsequences-gcds/solution/by-stormsunshine-mrrf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考代码2

class Solution {
public:
    int m = 0;
    bool f[200010];
    int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
    bool check(int x){
        int t = 0;
        for(int i = x; i <= m; i += x) 
            if(f[i]){
                if(t==0)t = i/x;
                else t=gcd(t,i/x);
            }
        return t == 1;
    }
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < n; ++i){
            m = max(m,nums[i]);
            f[nums[i]] = 1;
        }
        for(int i = 1;i <= m; ++i)
            if(check(i))
                ++ans;
        return ans;
    }
};

作者：Hankpipi
链接：https://leetcode.cn/problems/number-of-different-subsequences-gcds/solution/kao-lu-mei-yi-ge-shu-shi-fou-ke-yi-cheng-2sb2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。