Hard

题目描述

给你一个 m x n 的正整数矩阵 mat。

返回一个整数，表示从 mat 的每一行中恰好选择一个整数，使得所有选择的整数的最大公约数为 1 的方案数。

由于答案可能非常大，请返回答案对 10^9 + 7 取模的结果。

示例 1：

输入：mat = [[1,2],[3,4]]
输出：3
解释：
选择的组合及其最大公约数：
- 第一行选1，第二行选3，最大公约数为1
- 第一行选1，第二行选4，最大公约数为1  
- 第一行选2，第二行选3，最大公约数为1
- 第一行选2，第二行选4，最大公约数为2

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

示例 2：

输入：mat = [[2,2],[2,2]]
输出：0
解释：
每种组合的最大公约数都是2，因此答案是0。

约束条件：

  • 1 <= m == mat.length <= 150
  • 1 <= n == mat[i].length <= 150
  • 1 <= mat[i][j] <= 150

解题思路

这是一个典型的动态规划问题，核心思路是逐行处理，维护每种可能的最大公约数的方案数。

算法思路：

  1. 状态定义：使用 dp[row][gcd] 表示处理到第 row 行时，选择的数字的最大公约数为 gcd 的方案数。

  2. 初始化：第一行的每个数字 v 都可以作为起始状态，dp[0][v] = 1（如果有重复数字则累加）。

  3. 状态转移：对于第 i 行的每个数字 v，我们可以与前一行的每个可能的最大公约数 g 组合：

    • 新的最大公约数为 gcd(g, v)
    • 更新 dp[i][gcd(g, v)] += dp[i-1][g]

  4. 答案：最终答案是 dp[m-1][1]，即处理完所有行后最大公约数为1的方案数。

优化要点：

  • 由于矩阵元素最大为150，可能的最大公约数也不会超过150
  • 使用滚动数组优化空间复杂度
  • 注意取模运算防止溢出

时间复杂度：O(m × n × 最大值)，空间复杂度：O(最大值)

代码实现

class Solution {
public:
    int countCoprime(vector<vector<int>>& mat) {
        const int MOD = 1e9 + 7;
        int m = mat.size();
        
        // dp[g] 表示当前行中 gcd 为 g 的方案数
        vector<long long> dp(151, 0);
        
        // 初始化第一行
        for (int val : mat[0]) {
            dp[val] = (dp[val] + 1) % MOD;
        }
        
        // 处理后续行
        for (int i = 1; i < m; i++) {
            vector<long long> newDp(151, 0);
            
            for (int g = 1; g <= 150; g++) {
                if (dp[g] == 0) continue;
                
                for (int val : mat[i]) {
                    int newGcd = __gcd(g, val);
                    newDp[newGcd] = (newDp[newGcd] + dp[g]) % MOD;
                }
            }
            
            dp = newDp;
        }
        
        return dp[1];
    }
};

class Solution:
    def countCoprime(self, mat: List[List[int]]) -> int:
        MOD = 10**9 + 7
        m = len(mat)
        
        from math import gcd
        
        # dp[g] 表示当前行中 gcd 为 g 的方案数
        dp = [0] * 151
        
        # 初始化第一行
        for val in mat[0]:
            dp[val] = (dp[val] + 1) % MOD
        
        # 处理后续行
        for i in range(1, m):
            new_dp = [0] * 151
            
            for g in range(1, 151):
                if dp[g] == 0:
                    continue
                
                for val in mat[i]:
                    new_gcd = gcd(g, val)
                    new_dp[new_gcd] = (new_dp[new_gcd] + dp[g]) % MOD
            
            dp = new_dp
        
        return dp[1]

public class Solution {
    public int CountCoprime(int[][] mat) {
        const int MOD = 1000000007;
        int m = mat.Length;
        
        // dp[g] 表示当前行中 gcd 为 g 的方案数
        long[] dp = new long[151];
        
        // 初始化第一行
        foreach (int val in mat[0]) {
            dp[val] = (dp[val] + 1) % MOD;
        }
        
        // 处理后续行
        for (int i = 1; i < m; i++) {
            long[] newDp = new long[151];
            
            for (int g = 1; g <= 150; g++) {
                if (dp[g] == 0) continue;
                
                foreach (int val in mat[i]) {
                    int newGcd = GCD(g, val);
                    newDp[newGcd] = (newDp[newGcd] + dp[g]) % MOD;
                }
            }
            
            dp = newDp;
        }
        
        return (int)dp[1];
    }
    
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var countCoprime = function(mat) {
    const MOD = 1000000007;
    const m = mat.length;
    const n = mat[0].length;
    const MAX_VAL = 150;
    
    // Get all unique values from the matrix
    const uniqueVals = new Set();
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            uniqueVals.add(mat[i][j]);
        }
    }
    const vals = [...uniqueVals].sort((a, b) => a - b);
    
    // Precompute GCD
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    
    // Get divisors for each number
    const getDivisors = (num) => {
        const divisors = [];
        for (let i = 1; i * i <= num; i++) {
            if (num % i === 0) {
                divisors.push(i);
                if (i !== num / i) {
                    divisors.push(num / i);
                }
            }
        }
        return divisors.sort((a, b) => a - b);
    };
    
    // DP: dp[i][g] = number of ways to choose from first i rows with GCD g
    const dp = Array(m + 1).fill().map(() => new Map());
    dp[0].set(0, 1);
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const val = mat[i][j];
            for (const [prevGcd, ways] of dp[i]) {
                const newGcd = prevGcd === 0 ? val : gcd(prevGcd, val);
                dp[i + 1].set(newGcd, (dp[i + 1].get(newGcd) || 0) + ways);
                dp[i + 1].set(newGcd, dp[i + 1].get(newGcd) % MOD);
            }
        }
    }
    
    return dp[m].get(1) || 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n × V)，其中 m 是行数，n 是列数，V 是矩阵中的最大值（150）
空间复杂度O(V)，使用了大小为 151 的数组存储 dp 状态