针对 LeetCode 3725 题，最优雅高效的思路是容斥原理（逆向统计）。

由于矩阵元素最大只有150，我们可以先统计“最大公约数是 d 的倍数”的方案数，再用容斥倒推得到“恰好为1”的方案数。

核心算法思路

1. 预处理因子：预计算1..150每个数的所有因子。
2. 统计每行倍数计数：对每行统计能被d整除的数字个数 cnt[row][d]。
3. 计算倍数方案数：mul[d] = ∏ cnt[row][d]，即所有选中数都是d的倍数的方案数。
4. 容斥求恰好GCD：从大到小遍历d，exact[d] = mul[d] - sum(exact[2d], exact[3d], ...)。答案即 exact[1]。

Rust 实现代码

```rust
const MOD: i64 = 1_000_000_007;

impl Solution {
    pub fn count_coprime(mat: Vec<Vec<i32>>) -> i32 {
        let m = mat.len();
        let max_val = 150;
        let mut factors = vec![vec![]; max_val + 1];
        for d in 1..=max_val {
            for multiple in (d..=max_val).step_by(d) {
                factors[multiple].push(d);
            }
        }

        let mut cnt = vec![vec![0; max_val + 1]; m];
        for (i, row) in mat.iter().enumerate() {
            for &num in row {
                for &d in &factors[num as usize] {
                    cnt[i][d] += 1;
                }
            }
        }

        let mut mul = vec![0; max_val + 1];
        for d in 1..=max_val {
            let mut ways = 1;
            for i in 0..m {
                ways = (ways * cnt[i][d]) % MOD;
                if ways == 0 { break; }
            }
            mul[d] = ways;
        }

        let mut exact = vec![0; max_val + 1];
        for d in (1..=max_val).rev() {
            let mut sum = mul[d];
            for multiple in (d*2..=max_val).step_by(d) {
                sum = (sum - exact[multiple] + MOD) % MOD;
            }
            exact[d] = sum;
        }

        exact[1] as i32
    }
}
```

复杂度分析

· 时间复杂度：O(m * n * τ + V * log V)，其中V=150，τ为因子数。
· 空间复杂度：O(m * V)。

这种“容斥逆向思维”是解决此类问题的常见模式，也适用于CQOI 2015选数等经典题目。