针对 LeetCode 3725Golang 实现同样采用容斥原理逆向统计利用最大值只有150的特点高效求解。核心思路1. 预处理因子表枚举 1..150对每个倍数记录因子。2. 统计每行倍数计数对每行统计能被 d 整除的数字个数 cnt[row][d]。3. 计算倍数方案数mul[d] ∏ cnt[row][d]即每行选出的数都是 d 的倍数。4. 容斥求恰好GCD1从大到小遍历 dexact[d] mul[d] - sum(exact[2d], exact[3d], ...)。答案即 exact[1]。Golang 实现代码goconst MOD 1_000_000_007func countCoprime(mat [][]int) int {m : len(mat)maxVal : 150// 1. 预处理因子factors : make([][]int, maxVal1)for d : 1; d maxVal; d {for multiple : d; multiple maxVal; multiple d {factors[multiple] append(factors[multiple], d)}}// 2. 统计每行每个因子的出现次数cnt : make([][]int, m)for i : range cnt {cnt[i] make([]int, maxVal1)for _, num : range mat[i] {for _, d : range factors[num] {cnt[i][d]}}}// 3. 计算 mul[d]所有数都是 d 的倍数的方案数mul : make([]int, maxVal1)for d : 1; d maxVal; d {ways : 1for i : 0; i m; i {ways ways * cnt[i][d] % MODif ways 0 {break}}mul[d] ways}// 4. 容斥从大到小计算 gcd 恰好为 d 的方案数exact : make([]int, maxVal1)for d : maxVal; d 1; d-- {sum : mul[d]for multiple : d * 2; multiple maxVal; multiple d {sum (sum - exact[multiple] MOD) % MOD}exact[d] sum}return exact[1]}复杂度分析· 时间复杂度O(m * n * τ V * log V)其中 V150τ 为每个数的因子数平均约12个完全可接受。· 空间复杂度O(m * V)主要存储每行的因子计数。关键点说明· 由于数值范围固定为 1..150预计算因子表是最高效的方式。· 容斥从大到小计算保证 exact[multiple] 已经计算完毕。· 模运算使用 (sum - exact[multiple] MOD) % MOD 处理负数。这种方法比直接枚举所有组合快得多利用了数值范围小的特性进行反向计算。