列表

详情

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

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

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。

 

示例 1：

输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。

示例 2：

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

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int countDifferentSubsequenceGCDs(vector<int>& nums) { } };

python3 解法, 执行用时: 2288 ms, 内存消耗: 27 MB, 提交时间: 2023-01-14 11:01:34 

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

cpp 解法, 执行用时: 212 ms, 内存消耗: 69.6 MB, 提交时间: 2023-01-14 10:59:55 

class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int> &nums) {
        int ans = 0, mx = *max_element(nums.begin(), nums.end());
        bool has[mx + 1]; memset(has, 0, sizeof(has));
        for (int x : nums) has[x] = true;
        for (int i = 1; i <= mx; ++i) {
            int g = 0; // 0 和任何数 x 的最大公约数都是 x
            for (int j = i; j <= mx && g != i; j += i) // 枚举 i 的倍数 j
                if (has[j]) // 如果 j 在 nums 中
                    g = gcd(g, j); // 更新最大公约数
            if (g == i) ++ans; // 找到一个答案
        }
        return ans;
    }
};

java 解法, 执行用时: 42 ms, 内存消耗: 56.3 MB, 提交时间: 2023-01-14 10:59:36 

class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int ans = 0, mx = 0;
        for (int x : nums) mx = Math.max(mx, x);
        var has = new boolean[mx + 1];
        for (int x : nums)
            if (!has[x]) {
                has[x] = true;
                ++ans; // 单独一个数也算
            }
        for (int i = 1; i <= mx / 3; ++i) { // 优化循环上界
            if (has[i]) continue;
            int g = 0; // 0 和任何数 x 的最大公约数都是 x
            for (int j = i * 2; j <= mx && g != i; j += i) // 枚举 i 的倍数 j
                if (has[j]) // 如果 j 在 nums 中
                    g = gcd(g, j); // 更新最大公约数
            if (g == i) ++ans; // 找到一个答案
        }
        return ans;
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int tmp = a;
            a = b % a;
            b = tmp;
        }
        return b;
    }
}

java 解法, 执行用时: 53 ms, 内存消耗: 55.9 MB, 提交时间: 2023-01-14 10:59:25 

class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int ans = 0, mx = 0;
        for (int x : nums) mx = Math.max(mx, x);
        var has = new boolean[mx + 1];
        for (int x : nums) has[x] = true;
        for (int i = 1; i <= mx; ++i) {
            int g = 0; // 0 和任何数 x 的最大公约数都是 x
            for (int j = i; j <= mx && g != i; j += i) // 枚举 i 的倍数 j
                if (has[j]) // 如果 j 在 nums 中
                    g = gcd(g, j); // 更新最大公约数
            if (g == i) ++ans; // 找到一个答案
        }
        return ans;
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int tmp = a;
            a = b % a;
            b = tmp;
        }
        return b;
    }
}

golang 解法, 执行用时: 124 ms, 内存消耗: 8.7 MB, 提交时间: 2023-01-14 10:59:02 

func countDifferentSubsequenceGCDs(nums []int) (ans int) {
    mx := 0
    for _, x := range nums {
        if x > mx {
            mx = x
        }
    }
    has := make([]bool, mx+1)
    for _, x := range nums {
        if !has[x] {
            has[x] = true
            ans++
        }
    }
    for i := 1; i <= mx/3; i++ {
        if has[i] {
            continue
        }
        g := 0 // 0 和任何数 x 的最大公约数都是 x
        for j := i * 2; j <= mx && g != i; j += i { // 枚举 i 的倍数 j
            if has[j] { // 如果 j 在 nums 中
                g = gcd(g, j) // 更新最大公约数
            }
        }
        if g == i { // 找到一个答案
            ans++
        }
    }
    return
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

golang 解法, 执行用时: 132 ms, 内存消耗: 9.1 MB, 提交时间: 2023-01-14 10:58:48 

func countDifferentSubsequenceGCDs(nums []int) (ans int) {
    mx := 0
    for _, x := range nums {
        if x > mx {
            mx = x
        }
    }
    has := make([]bool, mx+1)
    for _, x := range nums {
        has[x] = true
    }
    for i := 1; i <= mx; i++ {
        g := 0 // 0 和任何数 x 的最大公约数都是 x
        for j := i; j <= mx && g != i; j += i { // 枚举 i 的倍数 j
            if has[j] { // 如果 j 在 nums 中
                g = gcd(g, j) // 更新最大公约数
            }
        }
        if g == i { // 找到一个答案
            ans++
        }
    }
    return
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

python3 解法, 执行用时: 1492 ms, 内存消耗: 27.2 MB, 提交时间: 2023-01-14 10:58:17 

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        ans, mx = 0, max(nums)
        has = [False] * (mx + 1)
        for x in nums:
            if not has[x]:
                has[x] = True
                ans += 1  # 单独一个数也算
        for i in range(1, mx // 3 + 1):  # 优化循环上界
            if has[i]: continue
            g = 0  # 0 和任何数 x 的最大公约数都是 x
            for j in range(i * 2, mx + 1, i):  # 枚举 i 的倍数 j
                if has[j]:  # 如果 j 在 nums 中
                    g = gcd(g, j)  # 更新最大公约数
                    if g == i:  # 找到一个答案（g 无法继续减小）
                        ans += 1
                        break  # 提前退出循环
        return ans

python3 解法, 执行用时: 2452 ms, 内存消耗: 27 MB, 提交时间: 2023-01-14 10:57:52 

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        ans, mx = 0, max(nums)
        has = [False] * (mx + 1)
        for x in nums: has[x] = True
        for i in range(1, mx + 1):
            g = 0  # 0 和任何数 x 的最大公约数都是 x
            for j in range(i, mx + 1, i):  # 枚举 i 的倍数 j
                if has[j]:  # 如果 j 在 nums 中
                    g = gcd(g, j)  # 更新最大公约数
                    if g == i:  # 找到一个答案（g 无法继续减小）
                        ans += 1
                        break  # 提前退出循环
        return ans

上一题

© 2024 leetcode.cn