# LeetCode - 1819. Number of Different Subsequences GCDs
### 題目網址：https://leetcode.com/problems/number-of-different-subsequences-gcds/
###### tags: `LeetCode` `Hard` `數學` `數論`

/*
    -LeetCode format-
    Problem: 1819. Number of Different Subsequences GCDs
    Difficulty: Hard
    
    by Inversionpeter
*/



static const auto Initialize = []{
    ios::sync_with_stdio(false); cout.tie(nullptr);
    return nullptr;
}();

inline int GCD(int a, int b) {
    static int buffer;
    while (b) {
        buffer = a;
        a = b;
        b = buffer % b;
    }
    return a;
}

bool haveNumber[200001];

class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        memset(haveNumber, false, sizeof(haveNumber));
        int maximum = 0, nowGCD, GCDs = 0;
        for (int &i : nums) {
            haveNumber[i] = true;
            maximum = max(maximum, i);
        }
        for (int i = 1; i <= maximum; ++i) {
            nowGCD = 0;
            for (int j = i; j <= maximum; j += i)
                if (haveNumber[j]) {
                    nowGCD = GCD(j, nowGCD);
                    if (nowGCD == i) {
                        ++GCDs;
                        break;
                    }
                }
        }
        return GCDs;
    }
};