3725. Count Ways to Choose Coprime Integers from Rows Hard

1/**
2 * [3725] Count Ways to Choose Coprime Integers from Rows
3 *
4 * You are given a m x n matrix mat of positive integers.
5 * Return an integer denoting the number of ways to choose exactly one integer from each row of mat such that the greatest common divisor of all chosen integers is 1.
6 * Since the answer may be very large, return it modulo 10^9 + 7.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">mat = [[1,2],[3,4]]</span>
11 * Output: <span class="example-io">3</span>
12 * Explanation:
13 * <table style="border: 1px solid black;">
14 * 	<tbody>
15 * 		<tr>
16 * 			<th align="center" style="border: 1px solid black;">Chosen integer in the first row</th>
17 * 			<th align="center" style="border: 1px solid black;">Chosen integer in the second row</th>
18 * 			<th align="center" style="border: 1px solid black;">Greatest common divisor of chosen integers</th>
19 * 		</tr>
20 * 		<tr>
21 * 			<td align="center" style="border: 1px solid black;">1</td>
22 * 			<td align="center" style="border: 1px solid black;">3</td>
23 * 			<td align="center" style="border: 1px solid black;">1</td>
24 * 		</tr>
25 * 		<tr>
26 * 			<td align="center" style="border: 1px solid black;">1</td>
27 * 			<td align="center" style="border: 1px solid black;">4</td>
28 * 			<td align="center" style="border: 1px solid black;">1</td>
29 * 		</tr>
30 * 		<tr>
31 * 			<td align="center" style="border: 1px solid black;">2</td>
32 * 			<td align="center" style="border: 1px solid black;">3</td>
33 * 			<td align="center" style="border: 1px solid black;">1</td>
34 * 		</tr>
35 * 		<tr>
36 * 			<td align="center" style="border: 1px solid black;">2</td>
37 * 			<td align="center" style="border: 1px solid black;">4</td>
38 * 			<td align="center" style="border: 1px solid black;">2</td>
39 * 		</tr>
40 * 	</tbody>
41 * </table>
42 * 3 of these combinations have a greatest common divisor of 1. Therefore, the answer is 3.
43 * </div>
44 * <strong class="example">Example 2:
45 * <div class="example-block">
46 * Input: <span class="example-io">mat = [[2,2],[2,2]]</span>
47 * Output: <span class="example-io">0</span>
48 * Explanation:
49 * Every combination has a greatest common divisor of 2. Therefore, the answer is 0.
50 * </div>
51 *  
52 * Constraints:
53 * 
54 * 	1 <= m == mat.length <= 150
55 * 	1 <= n == mat[i].length <= 150
56 * 	1 <= mat[i][j] <= 150
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/count-ways-to-choose-coprime-integers-from-rows/
62// discuss: https://leetcode.com/problems/count-ways-to-choose-coprime-integers-from-rows/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn count_coprime(mat: Vec<Vec<i32>>) -> i32 {
68        0
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_3725() {
80    }
81}
82