1819

1819. Number of Different Subsequences GCDs (Hard)

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:

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 <= 105
• 1 <= nums[i] <= 2 * 105

Related Topics:
Math

Solution 1.

// OJ: https://leetcode.com/problems/number-of-different-subsequences-gcds/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& A) {
        const int N = 2e5;
        int ans = 0;
        bool seen[N + 1] = {};
        for (int n : A) seen[n] = true;
        for (int i = 1; i <= N; ++i) {
            int div = 0;
            for (int j = i; j <= N; j += i) {
                if (seen[j]) div = gcd(div, j);
            }
            if (div == i) ++ans;
        }
        return ans;
    }
};