企业官网建设流程全解析

针对 LeetCode 3725，Golang 实现同样采用容斥原理（逆向统计），利用最大值只有150的特点高效求解。

核心思路

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

Golang 实现代码

```go
const MOD = 1_000_000_007

func countCoprime(mat [][]int) int {
m := len(mat)
maxVal := 150

// 1. 预处理因子
factors := make([][]int, maxVal+1)
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, maxVal+1)
for _, num := range mat[i] {
for _, d := range factors[num] {
cnt[i][d]++
}
}
}

// 3. 计算 mul[d]：所有数都是 d 的倍数的方案数
mul := make([]int, maxVal+1)
for d := 1; d <= maxVal; d++ {
ways := 1
for i := 0; i < m; i++ {
ways = ways * cnt[i][d] % MOD
if ways == 0 {
break
}
}
mul[d] = ways
}

// 4. 容斥：从大到小计算 gcd 恰好为 d 的方案数
exact := make([]int, maxVal+1)
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)，其中 V=150，τ 为每个数的因子数（平均约12个），完全可接受。
· 空间复杂度：O(m * V)，主要存储每行的因子计数。

关键点说明

· 由于数值范围固定为 1..150，预计算因子表是最高效的方式。
· 容斥从大到小计算，保证 exact[multiple] 已经计算完毕。
· 模运算使用 (sum - exact[multiple] + MOD) % MOD 处理负数。

这种方法比直接枚举所有组合快得多，利用了数值范围小的特性进行反向计算。