hardArrayDynamic ProgrammingMathNumber Theory 0 views
Find the Number of Subsequences With Equal GCD
You are given an integer array nums.
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:
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: 10
Explanation: The subsequence pairs which have the GCD of their elements equal to 1 are:
Example 2
Input: nums = [10,20,30]
Output: 2
Explanation: The subsequence pairs which have the GCD of their elements equal to 10 are:
Example 3
Input: nums = [1,1,1,1]
Output: 50
Constraints
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 200
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.