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
    }
}

执行结果如下：

在这里插入图片描述

左神java代码