1. 序列中不同最大公约数的数目
   困难

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

例如，序列 [4,6,16] 的最大公约数是 2 。
数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。

考虑枚举每个约数 看是否存在子序列的最大公约数 那么子序列的每个数一定都是约数的倍数才会满足条件

子序列中数的个数越多 最大公约数就越小！！！

class Solution {
public:
    bool st[200010];
    int gcd(int a, int b){
        return b ? gcd(b, a % b) : a;
    }
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int n = nums.size();
        int mx = 0;
        for(auto &x : nums) mx = max(mx, x), st[x] = true;
        int res = 0;
        for(int i = 1; i <= mx; i ++){
            int g = 0;
            for(int j = i; j <= mx; j += i){
                if(st[j]){
                    g = gcd(g, j);//子序列中的数越多，g 就可能越小，就越可能等于 i。
                    if(g == i){
                        res ++;
                        break;
                    }
                }
            }
        }
        return res;
    }
};