Count how many non-empty subsequences have the same greatest common divisor as the full array.
Problem
Given an integer array nums, count the number of non-empty subsequences whose greatest common divisor (GCD) is equal to the GCD of the entire array.
A subsequence is formed by deleting zero or more elements without changing the relative order of the remaining elements.
Return the count of such subsequences.
Because the answer can be large, return it modulo .
Notes
- The GCD of a subsequence is the GCD of all its elements.
- The subsequence may contain any number of elements as long as it is non-empty.
- You only need to count subsequences, not distinct sets of values.
Input Format
- An integer array
nums.
The exact platform signature may vary, but the task is to count subsequences satisfying the GCD condition.
Output Format
- Return an integer: the number of non-empty subsequences whose GCD equals the GCD of the whole array, modulo .
Constraints
- Elements are positive integers
- Answer should be computed modulo
Exact official bounds are not provided in the source metadata, so these are stated conservatively.
Example 1
Input
nums = [3, 6, 9]
Output
5
Explanation
The GCD of the whole array is 3. The subsequences with GCD 3 are: [3], [6, 9], [3, 6], [3, 9], and [3, 6, 9].
Example 2
Input
nums = [2, 4, 6]
Output
5
Explanation
The GCD of the whole array is 2. The valid subsequences are [2], [2, 4], [2, 6], [4, 6], and [2, 4, 6].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.