Problem: 8026. 构造乘积矩阵

[TOC]

思路

本题最简单的解法是前缀后缀积的解法，因为已经有很多题解了，这里就不提了。比赛的时候我一直想基于扩展欧几里得算法求逆元来求解，但是细节没有处理好，比赛没有通过。赛后参考@雪景式大佬的逆元解法，才把细节处理好。

解题方法

由于本题要求每个位置除自己以外的元素乘积，很自然的会想到使用总乘积除以当前位置数字的解法。由于数字太大，需要取模，但是本题的模是12345，不是一个质数，我们在分母的数字是没有办法直接使用费马小定理来求逆元的，也就是$p=12345$时，$a^{p-2}\mod p$是无法求得$a$正确的逆元的。

对于$p=12345$，这种不是质数的，我们可以基于扩展欧几里得算法求逆元，由于扩展欧几里得算法需要互质，而$12345= 35823$, 我们需要对矩阵中是这三个质数倍数的数字做处理，将3,5,823的计数存下来，而对应的数字需要除掉所有的3,5,823的因数，再去做矩阵中所有数字的乘积，用于后面和逆元相乘，得到当前位置的结果。

接着就是如何使用扩展欧几里得算法得到当前矩阵位置数字除掉3,5,823后数值$a$的逆元了。
根据裴蜀定理，如果$a,m$互质，则有：$ax+my = 1$,此时$ax \equiv 1(\mod m)$, 也就是$x$就是$a$的逆元，我们可以辗转相除法求出$a,m$的最大公因数$gcd(a,m)$,在这个过程中对应的系数$x,y$就可以求出来，而$x$就是我们要的逆元。具体可以参考下面ex_gcd和inv两个函数。

当我们求出每个位置的逆元后，就可以求结果了：

• 对于除了当前位置以外，还有可以同时被3,5,823整除，即被12345整除的因数，直接返回结果0
• 对于除了当前位置以外，不能被12345整除的因数，则用总乘积乘以当前位置的逆元，还需要乘以剩下所有的3（若有）,5（若有）,823（若有）,最后乘以剩下的3,5,823的幂的部分要使用快速幂。

复杂度

• 时间复杂度:$O(mn\log U)$,其中$\log U$为扩展欧几里得算法和快速幂的复杂度,这部分对数复杂度取决于矩阵中最大数字的大小，以及3,5,823的最大因数个数。
• 空间复杂度: $O(1)$

Code

###Java

class Solution {
    int MOD = 12345; //12345 = 3*5*823
    public int[][] constructProductMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int cnt3 = 0;
        int cnt5 = 0;
        int cnt823 = 0;
        long multiAll = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int[] tmp = numMod(grid[i][j]);
                cnt3 += tmp[0];
                cnt5 += tmp[1];
                cnt823 += tmp[2];
                multiAll = multiAll * tmp[3] % MOD;
            }
        }
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int[] tmp = numMod(grid[i][j]);
                if(cnt3-tmp[0] > 0 && cnt5-tmp[1] > 0 && cnt823-tmp[2] > 0) res[i][j] = 0;
                else{
                    long curRes = multiAll*inv(tmp[3], MOD)%MOD;
                    curRes = curRes*pow(3, cnt3-tmp[0])%MOD;
                    curRes = curRes*pow(5, cnt5-tmp[1])%MOD;
                    curRes = curRes*pow(823, cnt823-tmp[2])%MOD;
                    res[i][j] = (int)curRes;
                }
            }
        }
        return res;
    }
    //计算a^b%MOD
    private long pow(int a, int b){
        long res = 1;
        long a1 = a;
        while(b > 0){
            if((b&1) > 0) res =  (res*a1)%MOD;
            a1 = (a1*a1)%MOD;
            b = b/2;
        }
        return res;
    }
    public int[] numMod(int num){
        int cnt3Cur = 0;
        int cnt5Cur = 0;
        int cnt823Cur = 0;
        while(num%3 == 0){
            num /= 3;
            cnt3Cur++;
        }
        while(num%5 == 0){
            num /= 5;
            cnt5Cur++;
        }
        while(num%823 == 0){
            num /= 823;
            cnt823Cur++;
        }
        return new int[]{cnt3Cur, cnt5Cur, cnt823Cur, num};
    }
    //扩展欧几里得求逆元
    public int[] ex_gcd(int a, int b){
        if(b == 0) return new int[]{a,1,0};
        else {
            int[] res = ex_gcd(b, a%b);
            return new int[]{res[0], res[2], res[1]-(a/b)*res[2]};
        }
    }
    //保证a、m互质的情况下才可以使用
    public int inv(int a, int m){
        int[] res = ex_gcd(a, m);
        if(res[0]  != 1) return -1;
        return (res[1]+m)%m;
    }
}