Package g3701_3800.s3725_count_ways_to_choose_coprime_integers_from_rows

Class Solution

java.lang.Object

g3701_3800.s3725_count_ways_to_choose_coprime_integers_from_rows.Solution

public class Solution
extends Object

3725 - Count Ways to Choose Coprime Integers from Rows.

Hard

You are given a m x n matrix mat of positive integers.

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.

Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: mat = [[1,2],[3,4]]

Output: 3

Explanation:

Chosen integer in the first row	Chosen integer in the second row	Greatest common divisor of chosen integers
1	3	1
1	4	1
2	3	1
2	4	2

3 of these combinations have a greatest common divisor of 1. Therefore, the answer is 3.

Example 2:

Input: mat = [[2,2],[2,2]]

Output: 0

Explanation:

Every combination has a greatest common divisor of 2. Therefore, the answer is 0.

Constraints:

• 1 <= m == mat.length <= 150
• 1 <= n == mat[i].length <= 150
• 1 <= mat[i][j] <= 150

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	countCoprime(int[][] mat)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

countCoprime

public int countCoprime(int[][] mat)