Count ways to choose coprime integers from rows

Array Math Dynamic Programming Matrix Combinatorics Number Theory

48.3% acceptance

Feb 24, 2026

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 10^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_coprime(mat: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let _m = mat.len();
    // Use inclusion-exclusion via Mobius function
    // f(d) = number of ways to choose such that gcd is divisible by d
    //      = product over rows of (count of elements in row divisible by d)
    // Answer = sum_{d=1}^{150} mu(d) * f(d)
    let max_val = 150usize;
    // Compute Mobius function
    let mut mu = vec![0i32; max_val + 1];
    mu[1] = 1;
    let mut primes = vec![];
    let mut is_composite = vec![false; max_val + 1];
    for i in 2..=max_val {
      if !is_composite[i] {
        primes.push(i);
        mu[i] = -1;
      }
      for &p in &primes {
        if i * p > max_val { break; }
        is_composite[i * p] = true;
        if i % p == 0 {
          mu[i * p] = 0;
          break;
        } else {
          mu[i * p] = -mu[i];
        }
      }
    }
    // For each d, compute product of count of multiples of d in each row
    let mut ans = 0i64;
    for d in 1..=max_val {
      if mu[d] == 0 { continue; }
      let mut prod = 1i64;
      for row in &mat {
        let cnt = row.iter().filter(|&&x| x as usize % d == 0).count() as i64;
        prod = prod * cnt % MOD;
        if prod == 0 { break; }
      }
      if mu[d] == 1 {
        ans = (ans + prod) % MOD;
      } else {
        ans = (ans - prod + MOD) % MOD;
      }
    }
    ans as i32
  }
}