Find the Number of Subsequences With Equal GCD - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3336. Find the Number of Subsequences With Equal GCD
Hard
50 Points
Array
Math
Dynamic Programming
Number Theory
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 109 + 7.
Examples
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
3336. Find the Number of Subsequences With Equal GCD
Hard
50 Points
Array
Math
Dynamic Programming
Number Theory
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 109 + 7.
Examples
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: