以下是 LeetCode 3725 的 Python3 实现使用容斥原理 DP思路与 Java 版本一致pythonfrom typing import Listclass Solution:def countCoprime(self, mat: List[List[int]]) - int:MOD 10**9 7MAX_VAL 150# 1. 预处理每个数的所有因子divisors [[] for _ in range(MAX_VAL 1)]for d in range(1, MAX_VAL 1):for multiple in range(d, MAX_VAL 1, d):divisors[multiple].append(d)m len(mat)# 2. 统计每行中能被 d 整除的数字个数row_divisor_cnt [[0] * (MAX_VAL 1) for _ in range(m)]for i in range(m):for x in mat[i]:for d in divisors[x]:row_divisor_cnt[i][d] 1# 3. 容斥计算gcd恰好为d的方案数exact_gcd [0] * (MAX_VAL 1)for d in range(MAX_VAL, 0, -1):ways 1for i in range(m):ways (ways * row_divisor_cnt[i][d]) % MODif ways 0:break# 减去 gcd 是 d 的倍数的方案for multiple in range(2 * d, MAX_VAL 1, d):ways (ways - exact_gcd[multiple]) % MODexact_gcd[d] waysreturn exact_gcd[1] % MOD核心思路说明1. 正向计算row_divisor_cnt[i][d] 表示第 i 行中能被 d 整除的数字个数。那么所有行都选 d 的倍数的方案数为 ∏ row_divisor_cnt[i][d]。2. 容斥去重· ∏ row_divisor_cnt[i][d] 实际上统计的是 gcd 为 d、2d、3d... 的所有方案· 从大到小遍历 d用 ways 减去所有 exact_gcd[multiple]multiple 是 d 的倍数剩下的就是 gcd 恰好为 d 的方案数3. 为什么从大到小因为计算 exact_gcd[d] 需要用到 exact_gcd[2d]、exact_gcd[3d] 等更大的数所以必须逆序计算。复杂度分析· 时间复杂度O(m * n * τ V²)其中 V150τ 是每个数的因子个数≤12· 空间复杂度O(m * V)