Leetcode每日一题 20240730 2961.双模幂运算

题目描述

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

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

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

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

2961.双模幂运算

测试案例及提示

示例 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³
0 <= target <= 10³

解题思路

读一遍题目下来，需要输出的是一个好下标组成的数组。
而一个好下标要满足两个条件，第二个条件涉及到幂和模运算。
在python中，提供了pow函数，可以同时进行幂运算和模运算。
在其他语言中，也可以通过使用快速幂的方法达到相近的效果。
python

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        ans = []
        n = len(variables)
        for i, c in enumerate(variables):
            if pow(pow(c[0], c[1], 10), c[2], c[3]) == target:
                ans.append(i)
        return ans

C

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int powMod(int x, int y, int mod);
int* getGoodIndices(int** variables, int variablesSize, int* variablesColSize, int target, int* returnSize) {
    int* ans = (int *) malloc (variablesSize * sizeof(int));
    int j = 0;

    for (int i = 0; i < variablesSize; i++) {
        int a = variables[i][0];
        int b = variables[i][1];
        int c = variables[i][2];
        int m = variables[i][3];
        if (powMod(powMod(a, b, 10), c, m) == target) {
            ans[j] = i;
            j++;
        }
    }

    *returnSize = j;
    return ans;
}

int powMod(int x, int y, int mod) {
    int ans = 1;

    while (y > 0) {
        if (y & 1) {
            ans = ans * x % mod;
        }
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}