2026-03-17：统计每一行选择互质整数的方案数。用go语言，给定一个由正整数构成的矩阵，尺寸为 m × n。 从矩阵的每一行中各选取一个数，得到 m 个被选数字。 统计这样的选法数量，使得这些被

2026-03-17：统计每一行选择互质整数的方案数。用go语言，给定一个由正整数构成的矩阵，尺寸为 m × n。

从矩阵的每一行中各选取一个数，得到 m 个被选数字。

统计这样的选法数量，使得这些被选数字的最大公约数为 1。

由于结果可能很大，答案需对 1000000007 取模后返回。

1 <= m == mat.length <= 150。

1 <= n == mat[i].length <= 150。

1 <= mat[i][j] <= 150。

输入: mat = [[1,2],[3,4]]。

输出: 3。

解释:

其中 3 种组合的最大公约数为 1。因此，答案是 3。

题目来自力扣3725。

一、算法整体思路（容斥原理+莫比乌斯反演思想）

直接统计gcd=1的方案很难，我们用逆向思维：

二、分步骤详细执行过程

步骤1：预处理1~150所有数的因子（全局初始化）

因为矩阵元素最大值是150，提前计算好 1 到 150 每个数字的所有正因子，存入数组备用。

• 遍历 1~150 每个数 i；
• 把 i 作为因子，添加到所有 i 的倍数（i、2i、3i…）的因子列表中；
• 最终得到：每个数 x 对应的所有因子（如 6 的因子是 [1,2,3,6]）。

步骤2：统计矩阵每行中，每个因子的出现次数

对矩阵的每一行单独处理，统计这一行里：能被 d 整除的数字有多少个（d 是所有可能的因子）。

示例：
第一行 [1,2]：

• 因子1：2个数都能被1整除 → 计数=2
• 因子2：1个数能被2整除 → 计数=1
  第二行 [3,4]：
• 因子1：2个数都能被1整除 → 计数=2
• 因子3：1个数能被3整除 → 计数=1
• 因子4：1个数能被4整除 → 计数=1

步骤3：计算「所有数都能被d整除」的总选法数

根据乘法原理：从每行选1个能被d整除的数，总方案数 = 每行的可选数量相乘。

• 遍历每一行的d因子计数；
• 若某一行没有能被d整除的数，总方案数直接为0；
• 否则所有行的计数相乘，得到所有选中数都是d的倍数的总方案数。

示例：
d=1：第一行可选2个，第二行可选2个 → 总方案=2×2=4
d=2：第一行可选1个，第二行可选1个 → 总方案=1×1=1
d=3：第一行可选0个 → 总方案=0
d=4：第一行可选0个 → 总方案=0

步骤4：从大到小去重，计算「恰好gcd=d」的方案数

这是核心步骤：我们之前算的是gcd是d的倍数的方案数，需要剔除gcd更大的方案，得到恰好gcd=d的方案数。

示例：

• 最大数是4，先算d=4、3、2，最后算d=1；
• d=2：总方案1，无更大倍数 → 恰好gcd=2的方案数=1；
• d=1：总方案4，减去d=2的方案数1 → 恰好gcd=1的方案数=3。

步骤5：输出最终结果

恰好gcd=1的方案数就是答案，为了保证结果非负，最终再取一次模。

四、时间复杂度分析

我们拆分所有步骤的耗时：

总时间复杂度

O(maxVal² + m×n×maxVal)
代入题目限制（m,n,maxVal≤150），总操作数约 340万，效率极高。

五、额外空间复杂度分析

额外空间指除输入矩阵外开辟的所有存储空间：

总额外空间复杂度

O(m×maxVal + maxVal)
代入限制，空间占用极小，完全满足题目要求。

总结

Go完整代码如下：

package main

import (
"fmt"
"slices"
)

const maxVal = 151

var divisors [maxVal][]int

func init() {
for i := 1; i < maxVal; i++ {
for j := i; j < maxVal; j += i {
divisors[j] = append(divisors[j], i)
}
}
}

func countCoprime(mat [][]int) int {
const mod = 1_000_000_007
// 预处理每行的因子个数
divisorCnt := make([][]int, len(mat))
mx := 0
for i, row := range mat {
rowMax := slices.Max(row)
mx = max(mx, rowMax)
divisorCnt[i] = make([]int, rowMax+1)
for _, x := range row {
for _, d := range divisors[x] {
divisorCnt[i][d]++
}
}
}

cntGcd := make([]int, mx+1)
for i := mx; i > 0; i— {
// 每行选一个 i 的倍数的方案数
res := 1
for _, cnt := range divisorCnt {
if i >= len(cnt) || cnt[i] == 0 {
res = 0
break
}
res = res * cnt[i] % mod // 乘法原理
}

for j := i; j <= mx; j += i {
res -= cntGcd[j] // 注意这里有减法，可能导致 res 是负数
}

cntGcd[i] = res % mod
}
return (cntGcd[1] + mod) % mod // 保证结果非负
}

func main() {
mat := [][]int{{1, 2}, {3, 4}}
result := countCoprime(mat)
fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

MOD = 1_000_000_007
MAX_VAL = 151

# 预处理每个数的因子
divisors = [[] for _ in range(MAX_VAL)]
for i in range(1, MAX_VAL):
for j in range(i, MAX_VAL, i):
divisors[j].append(i)

def count_coprime(mat):
# 预处理每行的因子计数
divisor_cnt = []
mx = 0

for row in mat:
row_max = max(row)
mx = max(mx, row_max)
# 创建当前行的计数数组，长度为 row_max + 1
row_cnt = [0] * (row_max + 1)
for x in row:
for d in divisors[x]:
if d <= row_max:
row_cnt[d] += 1
divisor_cnt.append(row_cnt)

cnt_gcd = [0] * (mx + 1)

# 从大到小计算
for i in range(mx, 0, –1):
# 每行选一个 i 的倍数的方案数
res = 1
for row_cnt in divisor_cnt:
if i >= len(row_cnt) or row_cnt[i] == 0:
res = 0
break
res = (res * row_cnt[i]) % MOD

# 减去 gcd 大于 i 的方案数
for j in range(i * 2, mx + 1, i):
res = (res – cnt_gcd[j]) % MOD

cnt_gcd[i] = res

# 确保结果非负
return (cnt_gcd[1] + MOD) % MOD

def main():
mat = [[1, 2], [3, 4]]
result = count_coprime(mat)
print(result)

if __name__ == "__main__":
main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_VAL = 151;
const int MOD = 1'000'000'007;

vector<int> divisors[MAX_VAL];

// 初始化函数，预计算每个数的因子
void initDivisors() {
for (int i = 1; i < MAX_VAL; i++) {
for (int j = i; j < MAX_VAL; j += i) {
divisors[j].push_back(i);
}
}
}

int countCoprime(vector<vector<int>>& mat) {
// 预处理每行的因子个数
vector<vector<int>> divisorCnt(mat.size());
int mx = 0;

for (int i = 0; i < mat.size(); i++) {
int rowMax = *max_element(mat[i].begin(), mat[i].end());
mx = max(mx, rowMax);
divisorCnt[i].resize(rowMax + 1, 0);

for (int x : mat[i]) {
for (int d : divisors[x]) {
divisorCnt[i][d]++;
}
}
}

vector<int> cntGcd(mx + 1, 0);

// 从大到小计算
for (int i = mx; i > 0; i—) {
// 每行选一个 i 的倍数的方案数
long long res = 1;
for (auto& cnt : divisorCnt) {
if (i >= cnt.size() || cnt[i] == 0) {
res = 0;
break;
}
res = (res * cnt[i]) % MOD;
}

// 减去 gcd 大于 i 的方案数
for (int j = i * 2; j <= mx; j += i) {
res = (res – cntGcd[j] + MOD) % MOD;
}

cntGcd[i] = res % MOD;
}

return (cntGcd[1] + MOD) % MOD;
}

int main() {
// 初始化因子表
initDivisors();

vector<vector<int>> mat = {{1, 2}, {3, 4}};
int result = countCoprime(mat);
cout << result << endl;

return 0;
}