算法

(数学)

先开一个布尔数组 exist 来判断 nums 数组中的数是否存在，为后面枚举的剪枝做铺垫，然后可以考虑枚举每个可能的 gcd。

C++ 代码

class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int max = *max_element(nums.begin(), nums.end());
        vector<bool> exist(max + 1);
        for (auto x : nums) exist[x] = true;
        int ans = 0;
        for (int i = 1; i <= max; ++i) {
            int g = 0;
            for (int j = i; j <= max; j += i) {
                if (exist[j]) {
                    g = gcd(g, j);
                }
            }
            if (g == i) ans++;
        }
        return ans;
    }
};