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*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。