1819. Number of Different Subsequences GCDs Hard

1/**
2 * [1819] Number of Different Subsequences GCDs
3 *
4 * You are given an array nums that consists of positive integers.
5 * The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.
6 * 
7 * 	For example, the GCD of the sequence [4,6,16] is 2.
8 * 
9 * A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.
10 * 
11 * 	For example, [2,5,10] is a subsequence of [1,2,1,<u>2</u>,4,1,<u>5</u>,<u>10</u>].
12 * 
13 * Return the number of different GCDs among all non-empty subsequences of nums.
14 *  
15 * Example 1:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2021/03/17/image-1.png" style="width: 149px; height: 309px;" />
17 * Input: nums = [6,10,3]
18 * Output: 5
19 * Explanation: The figure shows all the non-empty subsequences and their GCDs.
20 * The different GCDs are 6, 10, 3, 2, and 1.
21 * 
22 * Example 2:
23 * 
24 * Input: nums = [5,15,40,5,6]
25 * Output: 7
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	1 <= nums.length <= 10^5
31 * 	1 <= nums[i] <= 2 * 10^5
32 * 
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/number-of-different-subsequences-gcds/
37// discuss: https://leetcode.com/problems/number-of-different-subsequences-gcds/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn count_different_subsequence_gc_ds(nums: Vec<i32>) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_1819() {
55    }
56}
57