Find the Number of Subsequences With Equal GCD
You are given an integer array nums.
Your task is to find the number of pairs of non-empty subsequences (seq1, seq2) of nums that satisfy the following conditions:
- The subsequences
seq1andseq2are disjoint, meaning no index ofnumsis common between them. - The GCD of the elements of
seq1is equal to the GCD of the elements ofseq2.
Return the total number of such pairs.
Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
nums = [1,2,3,4]Output
10There are 10 ordered pairs of disjoint non-empty subsequences whose GCDs are both equal to 1.
Example 2
Input
nums = [10,20,30]Output
2There are 2 ordered pairs of disjoint non-empty subsequences whose GCDs are both equal to 10.
Constraints
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 200