3336. Find the Number of Subsequences With Equal GCD Hard

1/**
2 * [3336] Find the Number of Subsequences With Equal GCD
3 *
4 * You are given an integer array nums.
5 * Your task is to find the number of pairs of non-empty <span data-keyword="subsequence-array">subsequences</span> (seq1, seq2) of nums that satisfy the following conditions:
6 * 
7 * 	The subsequences seq1 and seq2 are disjoint, meaning no index of nums is common between them.
8 * 	The <span data-keyword="gcd-function">GCD</span> of the elements of seq1 is equal to the GCD of the elements of seq2.
9 * 
10 * Return the total number of such pairs.
11 * Since the answer may be very large, return it modulo 10^9 + 7.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">nums = [1,2,3,4]</span>
16 * Output: <span class="example-io">10</span>
17 * Explanation:
18 * The subsequence pairs which have the GCD of their elements equal to 1 are:
19 * 
20 * 	([<u>1</u>, 2, 3, 4], [1, <u>2</u>, <u>3</u>, 4])
21 * 	([<u>1</u>, 2, 3, 4], [1, <u>2</u>, <u>3</u>, <u>4</u>])
22 * 	([<u>1</u>, 2, 3, 4], [1, 2, <u>3</u>, <u>4</u>])
23 * 	([<u>1</u>, <u>2</u>, 3, 4], [1, 2, <u>3</u>, <u>4</u>])
24 * 	([<u>1</u>, 2, 3, <u>4</u>], [1, <u>2</u>, <u>3</u>, 4])
25 * 	([1, <u>2</u>, <u>3</u>, 4], [<u>1</u>, 2, 3, 4])
26 * 	([1, <u>2</u>, <u>3</u>, 4], [<u>1</u>, 2, 3, <u>4</u>])
27 * 	([1, <u>2</u>, <u>3</u>, <u>4</u>], [<u>1</u>, 2, 3, 4])
28 * 	([1, 2, <u>3</u>, <u>4</u>], [<u>1</u>, 2, 3, 4])
29 * 	([1, 2, <u>3</u>, <u>4</u>], [<u>1</u>, <u>2</u>, 3, 4])
30 * </div>
31 * <strong class="example">Example 2:
32 * <div class="example-block">
33 * Input: <span class="example-io">nums = [10,20,30]</span>
34 * Output: <span class="example-io">2</span>
35 * Explanation:
36 * The subsequence pairs which have the GCD of their elements equal to 10 are:
37 * 
38 * 	([<u>10</u>, 20, 30], [10, <u>20</u>, <u>30</u>])
39 * 	([10, <u>20</u>, <u>30</u>], [<u>10</u>, 20, 30])
40 * </div>
41 * <strong class="example">Example 3:
42 * <div class="example-block">
43 * Input: <span class="example-io">nums = [1,1,1,1]</span>
44 * Output: <span class="example-io">50</span>
45 * </div>
46 *  
47 * Constraints:
48 * 
49 * 	1 <= nums.length <= 200
50 * 	1 <= nums[i] <= 200
51 * 
52 */
53pub struct Solution {}
54
55// problem: https://leetcode.com/problems/find-the-number-of-subsequences-with-equal-gcd/
56// discuss: https://leetcode.com/problems/find-the-number-of-subsequences-with-equal-gcd/discuss/?currentPage=1&orderBy=most_votes&query=
57
58// submission codes start here
59
60impl Solution {
61    pub fn subsequence_pair_count(nums: Vec<i32>) -> i32 {
62        0
63    }
64}
65
66// submission codes end
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn test_3336() {
74    }
75}
76