DeepSeek LeetCode 3725. 统计每一行选择互质整数的方案数 Rust实现

针对 LeetCode 3725 题最优雅高效的思路是容斥原理逆向统计。由于矩阵元素最大只有150我们可以先统计“最大公约数是 d 的倍数”的方案数再用容斥倒推得到“恰好为1”的方案数。核心算法思路1. 预处理因子预计算1..150每个数的所有因子。2. 统计每行倍数计数对每行统计能被d整除的数字个数 cnt[row][d]。3. 计算倍数方案数mul[d] ∏ cnt[row][d]即所有选中数都是d的倍数的方案数。4. 容斥求恰好GCD从大到小遍历dexact[d] mul[d] - sum(exact[2d], exact[3d], ...)。答案即 exact[1]。Rust 实现代码rustconst MOD: i64 1_000_000_007;impl Solution {pub fn count_coprime(mat: VecVeci32) - 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)其中V150τ为因子数。· 空间复杂度O(m * V)。这种“容斥逆向思维”是解决此类问题的常见模式也适用于CQOI 2015选数等经典题目。