题干描述
给你一个下标从 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 。 因此，返回 [] 作为答案。
题干解析
我们需要判断二维数组 variables 中的每个元素是否满足如下公式：
0 <= i < variables.length((aibi % 10)ci) % mi == target
如果满足，则该下标 i 是一个好下标，我们需要返回所有好下标的数组。
解题步骤
1.遍历每个元素：我们需要遍历variables数组中的每个元素[a_i, b_i, c_i, m_i]
2.计算中间结果
- 先计算 ai*bi%10
- 使用快速幂算法计算 （ai*bi%10）^ci%mi。
3.判断是否符合条件：如果上述计算结果等于target，则该下标是一个好下标。
4.记录好下标：将所有符合条件的下标记录到结果数组中。
5.返回结果：返回包含所有号下标的数组
代码实现
#include <stdio.h>
#include <stdlib.h>// 快速幂模运算函数：计算 (x^y) % mod
int pow_mod(int x, int y, int mod) {int res = 1;while (y) {if (y & 1) { // 如果 y 是奇数res = (res * x) % mod;}x = (x * x) % mod; // 平方底数y >>= 1; // 右移一位，相当于 y // 2}return res;
}/*** Note: The returned array must be malloced, assume caller calls free().* 函数：找到所有符合条件的好下标* @param variables: 二维整数数组，表示每个变量的值* @param variablesSize: 数组variables的大小* @param variablesColSize: 数组variables每一行的大小* @param target: 目标值* @param returnSize: 返回数组的大小* @return: 返回符合条件的好下标数组*/
int* getGoodIndices(int** variables, int variablesSize, int* variablesColSize, int target, int* returnSize) {int *ans = (int *)malloc(sizeof(int) * variablesSize); // 分配最大可能的空间int pos = 0; // 记录符合条件的下标个数for (int i = 0; i < variablesSize; i++) {int *v = variables[i];// 计算 (a_i * b_i % 10)int abMod10 = (v[0] * v[1]) % 10;// 计算 ((a_i * b_i % 10)^c_i % m_i)if (pow_mod(abMod10, v[2], v[3]) == target) {ans[pos++] = i;}}*returnSize = pos; // 设置返回的数组大小return ans;
}int main() {// 示例 1int variablesSize = 3;int variablesColSize[] = {4, 4, 4};int* variables[] = {(int[]){2, 3, 3, 10},(int[]){3, 3, 3, 1},(int[]){6, 1, 1, 4}};int target = 2;// 调用getGoodIndices函数，并获取结果int returnSize;int* result = getGoodIndices(variables, variablesSize, variablesColSize, target, &returnSize);// 输出结果数组printf("示例 1 结果: ");for (int i = 0; i < returnSize; i++) {printf("%d ", result[i]);}printf("\n");free(result);// 示例 2int variables2Size = 1;int variables2ColSize[] = {4};int* variables2[] = {(int[]){39, 3, 1000, 1000}};target = 17;// 调用getGoodIndices函数，并获取结果result = getGoodIndices(variables2, variables2Size, variables2ColSize, target, &returnSize);// 输出结果数组printf("示例 2 结果: ");for (int i = 0; i < returnSize; i++) {printf("%d ", result[i]);}printf("\n");free(result);return 0;
}
函数解释
1.pow_mod函数
- 使用快速幂算法计算（x^y）%mod.
- 通过不断平方底数并将指数减半来高效计算大幂次方的模运算结果。
2.getGoodIndices函数
- 遍历variables数组中的每个元素[a_i, b_i, c_i, m_i]。
- 首先计算ai*bi%10。
- 然后计算（ai*bi%10）^ci%mi，并与target进行比较。
- 如果相等，将当前下标i存入结果数组ans。
- 最后返回包含所有好下标的数组。