题目：
给你一个下标从 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] ，(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 <= 100variables[i] == [ai, bi, ci, mi]1 <= ai, bi, ci, mi <= 1030 <= target <= 103
最极致的模拟，最简单的思路
思路：
直接模拟运算过程就可以了
代码：
class Solution {
public:
vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
vector<int> ans;
for (int i = 0; i <variables.size(); i++) {
int a = variables[i][0], b = variables[i][1], c = variables[i][2], m = variables[i][3];
int temp = 1;
for (int j = 0; j < b; j++) {
temp = (temp * a) % 10;
}
int tmp = 1;
for (int j = 0; j < c; j++) {
tmp = (tmp * temp) % m;
}
if (target == tmp) {
ans.push_back(i);
}
}
return ans;
}
};
快速幂，加速运算
思路：
按题意扫描一遍 variables 数组进行模拟，找到满足要求的下标即可。在模拟时，使用了快速幂算法来计算幂运算。
「快速幂算法」的本质是分治算法。
举个例子，如果我们要计算 x^64 ，我们可以按照：x → x^2 → x^4 → x^8 → x^16 → x^32 → x^64的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 x^64 的值，而不需要对 x 乘 63 次 x。
再举一个例子，如果我们要计算 x^77 ，我们可以按照：x → x^2 → x^4 → x^9 → x^19 → x^38 → x^77 的顺序，在 x → x^2，x^2 → x^4 ，x^19 → x^38 这些步骤中，我们直接把上一次的结果进行平方，而在 x^4 → x^9，x^9 → x^19，x^38 → x^77 这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。
直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了：
当我们要计算 x^n 时，我们可以先递归地计算出 y = x^⌊n/2⌋，其中 ⌊a⌋ 表示对 a 进行下取整；
根据递归计算的结果，如果 n 为偶数，那么 x^n = y^2；如果 n 为奇数，那么 x^n = y^2 * x；
递归的边界为 n=0，任意数的 0 次方均为 1。
由于每次递归都会使得指数减少一半，因此递归的层数为 O(logn)，算法可以在很快的时间内得到结果。
代码：
class Solution {
public:
int pow_mod(int x, int y, int mod) {
int res = 1;
while (y) {
if (y & 1) {
res = res * x % mod;
}
x = x * x % mod;
y >>= 1;
}
return res;
}
vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
vector<int> ans;
for (int i = 0; i < variables.size(); i++) {
auto &v = variables[i];
if (pow_mod(pow_mod(v[0], v[1], 10), v[2], v[3]) == target) {
ans.push_back(i);
}
}
return ans;
}
};