这道题的核心思路是DP 容斥原理由于矩阵数值范围很小不超过150我们可以从d150向下计算“最大公约数恰好为d”的方案数。javaclass Solution {private static final int MOD 1_000_000_007;private static final int MAX_VAL 150;public int countCoprime(int[][] mat) {int m mat.length;// 1. 预处理每个数的所有因子ListInteger[] divisors new List[MAX_VAL 1];for (int i 1; i MAX_VAL; i) {divisors[i] new ArrayList();}for (int d 1; d MAX_VAL; d) {for (int multiple d; multiple MAX_VAL; multiple d) {divisors[multiple].add(d);}}// 2. 统计每行中能被 d 整除的数字个数int[][] rowDivisorCnt new int[m][MAX_VAL 1];for (int i 0; i m; i) {for (int x : mat[i]) {for (int d : divisors[x]) {rowDivisorCnt[i][d];}}}// 3. 容斥计算“gcd恰好为d”的方案数long[] exactGcd new long[MAX_VAL 1];for (int d MAX_VAL; d 1; d--) {long ways 1;for (int i 0; i m; i) {ways ways * rowDivisorCnt[i][d] % MOD;if (ways 0) break;}// 减去 gcd 是 d 的倍数的方案for (int multiple 2 * d; multiple MAX_VAL; multiple d) {ways (ways - exactGcd[multiple] MOD) % MOD;}exactGcd[d] ways;}return (int) exactGcd[1];}}核心思路说明这道题用容斥原理会更优雅比直接记忆化搜索更高效。· 正向转化先计算“所有选出的数都能被 d 整除”的方案数 totalWays(d)。因为每行只要选一个 d 的倍数即可用乘法原理就能算出。· 反向剔除totalWays(d) 其实统计的是 gcd d、2d、3d... 的方案总和。因此从大到小计算用 totalWays(d) 减去所有 gcd 是 d 倍数的方案数剩下的就是 gcd 恰好为 d 的方案数。· 高效预处理由于数值最大只有150提前把每个数的所有因子预处理出来。遍历矩阵时直接查表就能快速得到每行中能整除 d 的数字个数 cnt[i][d]。复杂度· 时间复杂度O(m * n * k V^2)其中 V150k 是因子个数很小。· 空间复杂度O(m * V)。
