力扣刷题之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] ，(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;
}