2022-09-07：给你一个由正整数组成的数组 nums 。数字序列的最大公约数定义为序列中所有整数的共有约数中的最大整数。例如，序列 [4,6,16] 的最大公约数是 2 。数组的一个

2022 年 9 月 07 日
北京
本文字数：1137 字
阅读完需：约 4 分钟

2022-09-07：给你一个由正整数组成的数组 nums 。数字序列的最大公约数定义为序列中所有整数的共有约数中的最大整数。例如，序列 [4,6,16] 的最大公约数是 2 。数组的一个子序列本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。计算并返回 nums 的所有非空子序列中不同最大公约数的数目。输入：nums = [5,15,40,5,6]；输出：7。

答案 2022-09-07：

n/1 + n/2 + n/3 + n/4 + ... + n/n 收敛于 O(N * logN)，N 是最大值，当做结论记住。

代码用 rust 编写。代码如下：

fn main() {    let mut arr = vec![5, 15, 40, 5, 6];    let ans = count_different_subsequence_gcds(&mut arr);    println!("ans = {}", ans);}
const MIN_VALUE: i32 = -1 << 31;
// n不是数字的个数，是数组中的最大值// 体系学习班，// 根据数据量猜解法，// 要想通过测试，一定要让计算量不超过10的7次方~10的8次方// n/1 + n/2 + n/3 + n/4 + ... + n/n -> O(N * logN)fn count_different_subsequence_gcds(nums: &mut Vec<i32>) -> i32 {    // 找到数组中的最大数！max    let mut max = MIN_VALUE;    for num in nums.iter() {        max = get_max(max, *num);    }    // 1~max，哪个数有哪个数没有    let mut set: Vec<bool> = vec![];    for _ in 0..max + 1 {        set.push(false);    }    for num in nums.iter() {        set[*num as usize] = true;    }    let mut ans = 0;    // a是当前想确定，是不是某个子序列的最大公约数，有a！    let mut a = 1;    while a <= max {        // 1)找到，离a最近的，a的倍数！1 2 3 ... g就是        let mut g = a;        while g <= max {            if set[g as usize] {                break;            }            g += a;        }        // 2) 找到了a最近的倍数，g        // g + 0 , g ?= a        // g + a , g ?= a        // g + 2a , g ?= a        // g + 3a , g ?= a        let mut b = g;        while b <= max {            if set[b as usize] {                g = gcd(g, b);                if g == a {                    ans += 1;                    break;                }            }            b += a;        }        a+=1;    }    return ans;}
fn gcd(m: i32, n: i32) -> i32 {    if n == 0 {        m    } else {        gcd(n, m % n)    }}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}