2961. 双模幂运算

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。

如果满足以下公式，则下标 i 是 好下标：

• 0 <= i < variables.length
• ((aibi % 10)ci) % mi == target

返回一个由 好下标 组成的数组，顺序不限 。

示例 1：

输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2

输出：[0,2]

解释：对于 variables 数组中的每个下标 i ： 1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(2³ % 10)³ % 10 = 2 。 2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(3³ % 10)³ % 1 = 0 。 3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(6¹ % 10)¹ % 4 = 2 。 因此，返回 [0,2] 作为答案。

示例 2：

输入：variables = [[39,3,1000,1000]], target = 17

输出：[]

解释：对于 variables 数组中的每个下标 i ： 1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(39³ % 10)¹⁰⁰⁰ % 1000 = 1 。 因此，返回 [] 作为答案。

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

    public int pow(int base, int exponent, int mod) {
        int result = 1;
        base = base % mod; // 首先将底数进行模运算，以防溢出
        while (exponent > 0) {
            // 如果指数是奇数，先乘以一次底数
            if (exponent % 2 == 1) {
                result = (result * base) % mod;
            }
            // 指数减半，底数平方
            exponent = exponent >> 1;
            base = (base * base) % mod;
        }
        return result;
    }
}