2183. Count Array Pairs Divisible by K Hard

1/**
2 * [2183] Count Array Pairs Divisible by K
3 *
4 * Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:
5 * 
6 * 	0 <= i < j <= n - 1 and
7 * 	nums[i] * nums[j] is divisible by k.
8 * 
9 *  
10 * Example 1:
11 * 
12 * Input: nums = [1,2,3,4,5], k = 2
13 * Output: 7
14 * Explanation: 
15 * The 7 pairs of indices whose corresponding products are divisible by 2 are
16 * (0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
17 * Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
18 * Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.    
19 * 
20 * Example 2:
21 * 
22 * Input: nums = [1,2,3,4], k = 5
23 * Output: 0
24 * Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	1 <= nums.length <= 10^5
30 * 	1 <= nums[i], k <= 10^5
31 * 
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/count-array-pairs-divisible-by-k/
36// discuss: https://leetcode.com/problems/count-array-pairs-divisible-by-k/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn count_pairs(nums: Vec<i32>, k: i32) -> i64 {
42        
43    }
44}
45
46// submission codes end
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn test_2183() {
54    }
55}
56