LeetCode 2961 双模幂运算

方法1：快速幂

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        ans = list()
        for i, (a, b, c, m) in enumerate(variables):
            res = self.getVal(a % 10, b)
            if pow(res, c, m) == target:
               ans.append(i)
        return ans

    def getVal(self, a: int, b: int) -> int:
        pair = {
            4: [6, 4],
            9: [1, 9],
            2: [6, 2, 4, 8],
            3: [1, 3, 9, 7],
            7: [1, 7, 9, 3],
            8: [6, 8, 4, 2]
        }
        if a == 0 or a == 1 or a == 5 or a == 6:
            return a
        elif a == 4 or a == 9:
            return pair[a][b % 2]
        else:
            return pair[a][b % 4]

class Solution {
    public List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> ans = new ArrayList<Integer>();
        for(int i = 0; i < variables.length; i++) {
            int res = getVal(variables[i][0] % 10, variables[i][1]);
            if (fastPow(res, variables[i][2], variables[i][3]) == target)
                ans.add(i);
        }
        return ans;
    }

    public int fastPow(int a, int b, int mod) {
        a %= mod; int ans = 1;
        while (b > 0) {
            if ((b & 1) == 1)
                ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return ans;
    }

    public int getVal(int a, int b) {
        int[][] pair = new int[][] {
            {0}, {1}, {6, 2, 4, 8}, {1, 3, 9, 7}, {6, 4},
            {5}, {6}, {1, 7, 9, 3}, {6, 8, 4, 2}, {1, 9}
        };
        if (a == 0 || a == 1 || a == 5 || a == 6)
            return pair[a][0];
        else if (a == 4 || a == 9)
            return pair[a][b % 2];
        else
            return pair[a][b % 4];
    }
}