无锡设计网站,网站安装php,广州天河区网站建设公司,成都知名网站推广Leetcode 2906. Construct Product Matrix 1. 解题思路2. 代码实现 题目链接#xff1a;2906. Construct Product Matrix
1. 解题思路
这道题其实算是一道数论题。
本来其实python的pow内置函数已经帮我们基本处理了所有的问题了#xff0c;但是这里稍微做了一点复杂化操…Leetcode 2906. Construct Product Matrix 1. 解题思路2. 代码实现 题目链接2906. Construct Product Matrix
1. 解题思路
这道题其实算是一道数论题。
本来其实python的pow内置函数已经帮我们基本处理了所有的问题了但是这里稍微做了一点复杂化操作给出的模是12345这是一个合数而不是一个质数因此并不总能保证对于任意一个数 x x x存在另一个数 y y y使得 x y ≡ 1 ( m o d 12345 ) xy \equiv 1 (mod \ 12345) xy≡1(mod 12345)但是我们只需要将 12345 12345 12345质因数分解为 12345 3 × 5 × 823 123453\times 5 \times 823 123453×5×823那么我们只需要对这三个因子进行单独考察即可。
2. 代码实现
给出python代码实现如下
class Solution:def constructProductMatrix(self, grid: List[List[int]]) - List[List[int]]:MOD 12345# 12345 3*5*823n, m len(grid), len(grid[0])prod, cnt 1, defaultdict(int)for i in range(n):for j in range(m):val grid[i][j]while val % 3 0:cnt[3] 1val val // 3while val % 5 0:cnt[5] 1val val // 5while val % 823 0:cnt[823] 1val val // 823prod prod * val % MODdef fn(i, j):val grid[i][j]cnt3 cnt[3]while val % 3 0:cnt3 - 1val val // 3cnt5 cnt[5]while val % 5 0:cnt5 - 1val val // 5cnt823 cnt[823]while val % 823 0:cnt823 - 1val val // 823return (prod * pow(val, -1, MOD) * pow(3, cnt3, MOD) * pow(5, cnt5, MOD) * pow(823, cnt823, MOD)) % MODreturn [[fn(i, j) for j in range(m)] for i in range(n)]提交代码评测得到耗时2361ms占用内存50.4MB。
