1819. Number of Different Subsequences GCDs

You are given an array nums that consists of positive integers.

The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.

• For example, the GCD of the sequence [4,6,16] is 2.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

• For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

Return the number of different GCDs among all non-empty subsequences of nums.

class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        unordered_set<int> us(begin(nums), end(nums));
        int res = 0;
        for(int i = 1; i <= 2e5; i++) {
            int gcd = 0;
            for(int j = i; j <= 2e5; j += i) {
                if(us.count(j)) gcd = __gcd(gcd,j);
                if(gcd == i) {
                    res++; break;
                }
            }
        }
        return res;
    }
};