# LeetCode 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`.

**Example 1:**![](https://assets.leetcode.com/uploads/2021/03/17/image-1.png)

```
Input: nums = [6,10,3]
Output: 5
Explanation: The figure shows all the non-empty subsequences and their GCDs.
The different GCDs are 6, 10, 3, 2, and 1.
```

**Example 2:**

```
Input: nums = [5,15,40,5,6]
Output: 7
```

**Constraints:**

* `1 <= nums.length <= 10^5`
* `1 <= nums[i] <= 2 * 10^5`

## Solution

[English Version in Youtube](https://youtu.be/Jbs6p2MLZjQ)

[中文版解答Youtube Link](https://youtu.be/ptaC4X0hC2Q)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1WX4y1g7sQ/)

```
class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int max_num = *max_element(nums.begin(), nums.end());
        vector<bool> vec(max_num + 1, false);
        for (int num: nums) {
            vec[num] = true;
        }
        int ans = 0;
        for (int i = 1; i <= max_num; i++) {
            int gcd = 0;
            for (int j = i; j <= max_num; j += i) {
                if (vec[j] == true) {
                    gcd = __gcd(gcd, j);
                }
            }
            if (gcd == i) ans++;
        }
        
        return ans;
    }
};
```
