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

链接：1819.序列中不同最大公约数的数目
难度：Hard
标签：数组、数学、计数、数论
简介：计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。

题解 1 - typescript

• 编辑时间：2022-01-07
• 执行用时：1948ms
• 内存消耗：67.2MB
• 编程语言：typescript
• 解法介绍：对于每个可能出现的最大公约数 i 进行统计，所有数中的 i 的倍数和的最大公约数是否为 i，是则存在。

function gcd(a: number, b: number) {
  if (b) return gcd(b, a % b);
  return a;
}
function countDifferentSubsequenceGCDs(nums: number[]): number {
  const set = new Set(nums);
  const max = Math.max(...nums);
  let ans = 0;
  for (let i = 1; i <= max; i++) {
    let val = -1;
    for (let j = i; j <= max; j += i) {
      if (!set.has(j)) continue;
      if (val == -1) val = j;
      else val = gcd(val, j);
    }
    if (val == i) ans++;
  }
  return ans;
}

题解 2 - cpp

• 编辑时间：2022-01-07
• 执行用时：292ms
• 内存消耗：70.1MB
• 编程语言：cpp
• 解法介绍：对于每个可能出现的最大公约数 i 进行统计，所有数中的 i 的倍数和的最大公约数是否为 i，是则存在。

class Solution {
   public:
    int gcd(int a, int b) {
        if (b) return gcd(b, a % b);
        return a;
    }
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int cnts[200005] = {0}, maxn = 0, ans = 0;
        for (auto& num : nums) {
            cnts[num] = 1;
            maxn = max(maxn, num);
        }
        for (int i = 1; i <= maxn; i++) {
            int val = -1;
            for (int j = i; j <= maxn; j += i) {
                if (!cnts[j]) continue;
                if (val == -1)
                    val = j;
                else
                    val = gcd(val, j);
            }
            if (val == i) ans++;
        }
        return ans;
    }
};

题解 3 - cpp

• 编辑时间：2023-01-14
• 执行用时：1156ms
• 内存消耗：114.2MB
• 编程语言：cpp
• 解法介绍：对每个数进行判断是否可能是最大公约数。

class Solution {
public:
    int gcd(int a, int b) {
        if (!b)return a;
        return gcd(b, a % b);
    }
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int n = nums.size(), ans = 0, nmax = 0;
        unordered_set<int> s;
        for (auto &num : nums) {
            nmax = max(nmax, num);
            s.insert(num);
        }
        vector<bool> l(nmax + 1, false);
        for (int i = 1; i <= nmax; i++) {
            if (s.count(i)) {
                ans++;
                continue;
            }
            int cur = -1;
            for (int j = 2; i * j <= nmax && cur != i; j++) {
                if (!s.count(i * j)) continue;
                if (cur == -1) cur = i * j;
                else cur = gcd(cur, i * j);
            }
            if (cur == i) ans++;
        }
        return ans;
    }
};

题解 4 - rust

• 编辑时间：2023-01-14
• 执行用时：60ms
• 内存消耗：3.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    fn gcd(a: i32, b: i32) -> i32 {
        if b == 0 {
            a
        } else {
            Solution::gcd(b, a % b)
        }
    }
    pub fn count_different_subsequence_gc_ds(nums: Vec<i32>) -> i32 {
        let mut max = 0;
        let mut ans = 0;
        let mut l = [false; 200005];
        for num in nums {
            max = max.max(num);
            l[num as usize] = true;
        }
        for i in 1..=max {
            if l[i as usize] {
                ans += 1;
                continue;
            }
            let mut j = 2;
            let mut cur = -1;
            while j * i <= max && cur != i {
                let num = i * j;
                if l[num as usize] {
                    cur = if cur == -1 {
                        num
                    } else {
                        Solution::gcd(cur, num)
                    }
                }
                j += 1;
            }
            if cur == i {
                ans += 1;
            }
        }
        ans
    }
}