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

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)
}

# -*-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()

#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;
}