Leetcode 2906. Construct Product Matrix

• Leetcode 2906. Construct Product Matrix
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2906. Construct Product Matrix

1. 解题思路

这道题其实算是一道数论题。

本来其实python的pow内置函数已经帮我们基本处理了所有的问题了，但是这里稍微做了一点复杂化操作，给出的模是12345，这是一个合数，而不是一个质数，因此并不总能保证对于任意一个数$x$，存在另一个数$y$使得$xy\equiv 1(mod12345)$，但是，我们只需要将$12345$质因数分解为$12345=3\times 5\times 823$，那么，我们只需要对这三个因子进行单独考察即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345
        # 12345 = 3*5*823
        
        n, 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] += 1
                    val = val // 3
                while val % 5 == 0:
                    cnt[5] += 1
                    val = val // 5
                while val % 823 == 0:
                    cnt[823] += 1
                    val = val // 823
                prod = prod * val % MOD
        
        def fn(i, j):
            val = grid[i][j]
            cnt3 = cnt[3]
            while val % 3 == 0:
                cnt3 -= 1
                val = val // 3
            cnt5 = cnt[5]
            while val % 5 == 0:
                cnt5 -= 1
                val = val // 5
            cnt823 = cnt[823]
            while val % 823 == 0:
                cnt823 -= 1
                val = val // 823
            return (prod * pow(val, -1, MOD) * pow(3, cnt3, MOD) * pow(5, cnt5, MOD) * pow(823, cnt823, MOD)) % MOD
        
        return [[fn(i, j) for j in range(m)] for i in range(n)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

提交代码评测得到：耗时2361ms，占用内存50.4MB。