1. 问题背景与需求拆解
今天遇到一个有趣的算法问题：给定一个m×n的整数矩阵，需要统计从每一行各选一个数，使得所有选出的数两两互质的方案总数。这个问题在组合数学和算法设计中具有一定代表性，特别是在需要处理多约束条件排列组合的场景下。
互质判定是数论基础概念，指两个数的最大公约数(GCD)为1。当扩展到多个数时，需要满足任意两个数都互质。举个例子，对于矩阵[[2,3],[4,5]]，有效方案有(2,5)和(3,4)和(3,5)，而(2,4)因为GCD(2,4)=2不互质，所以不算。
2. 核心算法思路分析
2.1 暴力解法与复杂度分析
最直观的做法是使用深度优先搜索(DFS)枚举所有可能的组合，然后逐一检查互质性。对于m行n列的矩阵，时间复杂度为O(n^m × m²)，因为：
- 组合数：n^m种可能
- 每组合检查：C(m,2)=m(m-1)/2对数字需要检查GCD
当m和n较大时（比如都达到10），n^m会爆炸式增长（10^10种组合），完全不可行。
2.2 动态规划优化思路
观察到互质关系具有传递性特征，可以采用动态规划记录已选数字的质因数集合。定义dp[i][S]表示前i行选出的数字的质因数并集为S时的方案数。
关键步骤：
- 预处理每行数字的质因数分解
- 初始化dp[0][∅] = 1
- 状态转移：对于第i行的每个数字，若其质因数与当前集合S无交集，则更新dp[i][S∪P] += dp[i-1][S]
- 最终结果为所有dp[m][S]之和
2.3 质因数处理的优化技巧
实际实现时，可以用位掩码表示质因数集合。但需要注意：
- 不同数字可能有相同质因数
- 大数分解质因数需要高效算法（Pollard's Rho）
- 可以预处理所有数字的质因数，建立质数到位的映射
3. Go语言实现详解
3.1 质因数分解实现
func primeFactors(x int) []int { factors := make([]int, 0) if x == 1 { return factors } for i := 2; i*i <= x; i++ { for x%i == 0 { factors = append(factors, i) x /= i } } if x > 1 { factors = append(factors, x) } return unique(factors) // 去重函数需自行实现 }3.2 动态规划主逻辑
func countCoprimeSelections(matrix [][]int) int { m := len(matrix) if m == 0 { return 0 } // 预处理每行数字的质因数 rowPrimes := make([][]map[int]bool, m) for i := range matrix { rowPrimes[i] = make([]map[int]bool, len(matrix[i])) for j, num := range matrix[i] { primes := primeFactors(num) rowPrimes[i][j] = make(map[int]bool) for _, p := range primes { rowPrimes[i][j][p] = true } } } // 初始化DP dp := make([]map[int]bool, 0) dp = append(dp, make(map[int]bool)) // 初始空集 for i := 0; i < m; i++ { newDp := make([]map[int]bool, 0) for _, currSet := range dp { for j := 0; j < len(matrix[i]); j++ { conflict := false for p := range rowPrimes[i][j] { if currSet[p] { conflict = true break } } if !conflict { newSet := cloneSet(currSet) // 深拷贝函数需自行实现 for p := range rowPrimes[i][j] { newSet[p] = true } newDp = append(newDp, newSet) } } } dp = newDp } return len(dp) }4. 性能优化实践
4.1 位掩码替代集合
当质数数量有限时（比如<64），可以用uint64表示质数集合：
var primeToBit = make(map[int]uint64) // 预先生成质数到位掩码的映射 func setToMask(primes []int) uint64 { var mask uint64 for _, p := range primes { mask |= primeToBit[p] } return mask }4.2 记忆化搜索优化
对于大规模矩阵，可以采用记忆化搜索+剪枝：
func backtrack(row int, usedPrimes uint64, memo map[pair]int) int { if row == m { return 1 } if val, exists := memo[pair{row, usedPrimes}]; exists { return val } total := 0 for _, num := range matrix[row] { mask := numToMask[num] if mask & usedPrimes == 0 { total += backtrack(row+1, usedPrimes | mask, memo) } } memo[pair{row, usedPrimes}] = total return total }5. 边界情况处理
实际编码时需要特别注意：
- 空矩阵或单行矩阵的处理
- 包含数字1的情况（1与任何数互质）
- 大质数处理（分解质因数效率）
- 去重处理（如矩阵中有重复数字）
6. 测试用例设计
完整测试应包含：
- 常规用例：如[[2,3],[4,5]] → 3
- 边界用例：[[1]] → 1， [[]] → 0
- 性能用例：10×10矩阵，数字范围1-100
- 特殊用例：包含相同数字的行，如[[2,2],[3,3]]
7. 复杂度对比
优化前后对比：
- 暴力法：O(n^m × m²)
- DP法：O(m × n × 2^k)，k为质数个数
- 位掩码优化：O(m × n × k)
当k较小时（质数数量少），优化效果显著。对于数字范围在1-100的矩阵，不同质数只有25个，实际运行效率很高。
8. 扩展思考
这个问题可以延伸到：
- 概率计算：随机选取时的互质概率
- 最大公约数约束：改为GCD为特定值
- 多维度约束：同时满足多个数论条件
- 分布式计算：超大规模矩阵的并行处理
在实际工程中，类似的组合约束问题常见于：
- 密码学中的密钥组合选择
- 调度系统中的资源分配
- 生物信息学的序列分析
通过这个问题，我们不仅学习了数论与动态规划的结合应用，更掌握了如何将数学洞察转化为高效算法的重要思维方法。在面试或竞赛中，这类问题往往考察的就是能否从暴力解法中识别出优化模式的能力。
