Challenge

Problem

Solutions

Submissions

Count Ways to Choose Coprime Integers from Rows

Challenge Points: 30

Level: Hard

You are given a 2D matrix mat of size m x n, where each element is a positive integer.
Your task is to count how many different ways you can choose exactly one number from each row so that the greatest common divisor (GCD) of all the selected numbers equals 1.

Since the total number of ways can be large, return the result modulo 10⁹ + 7.

Example 1:

Input: mat = [[2, 6], [3, 9]]

Output: 2

Explanation:

Possible selections and their GCDs: (2, 3) → 1 (2, 9) → 1 (6, 3) → 3 (6, 9) → 3 Only 2 combinations have GCD = 1.

Example 2:

Input: mat = [[4, 8], [6, 12]]

Output: 0

Explanation:

Every possible selection results in a GCD greater than 1. Hence, there are no valid combinations.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result