目标
给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。
如果满足以下公式，则下标 i 是 好下标：
- 0 <= i < variables.length
- ((ai^bi % 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] ，(23 % 10)3 % 10 = 2 。
2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(33 % 10)3 % 1 = 0 。
3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(61 % 10)1 % 4 = 2 。
因此，返回 [0,2] 作为答案。示例 2：
输入：variables = [[39,3,1000,1000]], target = 17
输出：[]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(393 % 10)1000 % 1000 = 1 。
因此，返回 [] 作为答案。说明：
- 1 <= variables.length <= 100
- variables[i] == [ai, bi, ci, mi]
- 1 <= ai, bi, ci, mi <= 10^3
- 0 <= target <= 10^3
思路
已知二维数组 variables[i] = [ai, bi, ci, mi]，定义好下标为 ((ai^bi % 10)^ci) % mi == target，返回好下标组成的数组。
尝试使用Math.pow暴力求解，存在精度丢失，例如 Math.pow(31, 12) = 7.8766278378854976 E17 ，mod 10 结果为 0。
提前mod也没用，比如 ai^bi % 10 == 6，6 ^ 83 % 81还是会丢失精度，只能手动循环计算了。
官网题解使用了快速幂。不用一个一个的乘，使用递归，根据幂的奇偶，偶数直接求 x^(n/2) * x^(n/2)，奇数求 x^(⌊n/2⌋) * x^(⌊n/2⌋) * x，直到n为0。时间复杂度为 O(logn)。
//todo 快速幂
代码
/**
* @date 2024-07-30 9:11
*/
public class GetGoodIndices2961 {
public List<Integer> getGoodIndices(int[][] variables, int target) {
List<Integer> res = new ArrayList<>();
int n = variables.length;
for (int i = 0; i < n; i++) {
int[] variable = variables[i];
int base = variable[0];
int tmp1 = 1;
for (int j = 0; j < variable[1]; j++) {
tmp1 = (tmp1 * base) % 10;
}
base = tmp1;
int tmp = 1;
for (int j = 0; j < variable[2]; j++) {
tmp = (tmp * base) % variable[3];
}
if (tmp % variable[3] == target) {
res.add(i);
}
}
return res;
}
}
性能
