Medium

题目描述

给你一个下标从 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]，(2^3 % 10)^3 % 10 = 2。
2) 对于下标 1，variables[1] = [3,3,3,1]，(3^3 % 10)^3 % 1 = 0。
3) 对于下标 2，variables[2] = [6,1,1,4]，(6^1 % 10)^1 % 4 = 2。
因此我们返回 [0,2] 作为答案。

示例 2：

输入：variables = [[39,3,1000,1000]], target = 17
输出：[]
解释：对于 variables 数组中的每个下标 i：
1) 对于下标 0，variables[0] = [39,3,1000,1000]，(39^3 % 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

解题思路

这道题需要计算双重模幂运算：((a^b % 10)^c) % m。

核心思路：

  1. 对于每个变量组 [a, b, c, m]，需要分两步计算：

    • 先计算 a^b % 10，得到第一层结果
    • 再计算 (第一层结果)^c % m，得到最终结果

  2. 关键优化 - 快速幂算法： 由于指数可能很大（最大1000），直接计算幂次会导致数值溢出或超时。使用快速幂算法可以在 O(log n) 时间内计算模幂运算。

  3. 实现步骤：

    • 遍历所有变量组
    • 使用快速幂计算 pow(a, b) % 10
    • 使用快速幂计算 pow(第一步结果, c) % m
    • 判断结果是否等于目标值

快速幂的原理是利用二进制分解：a^n = a^(n/2) * a^(n/2) * a^(n%2)，通过递归或迭代实现。

时间复杂度： O(n * log(max(b, c)))，其中 n 是变量组数量 空间复杂度： O(1)

代码实现

class Solution {
public:
    long long fastPow(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
    
    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
        vector<int> result;
        
        for (int i = 0; i < variables.size(); i++) {
            int a = variables[i][0];
            int b = variables[i][1];
            int c = variables[i][2];
            int m = variables[i][3];
            
            // 计算 (a^b % 10)^c % m
            long long firstStep = fastPow(a, b, 10);
            long long secondStep = fastPow(firstStep, c, m);
            
            if (secondStep == target) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        def fast_pow(base, exp, mod):
            result = 1
            base %= mod
            while exp > 0:
                if exp & 1:
                    result = (result * base) % mod
                base = (base * base) % mod
                exp >>= 1
            return result
        
        result = []
        
        for i, (a, b, c, m) in enumerate(variables):
            # 计算 (a^b % 10)^c % m
            first_step = fast_pow(a, b, 10)
            second_step = fast_pow(first_step, c, m)
            
            if second_step == target:
                result.append(i)
        
        return result

public class Solution {
    private long FastPow(long baseNum, long exp, long mod) {
        long result = 1;
        baseNum %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * baseNum) % mod;
            }
            baseNum = (baseNum * baseNum) % mod;
            exp >>= 1;
        }
        return result;
    }
    
    public IList<int> GetGoodIndices(int[][] variables, int target) {
        IList<int> result = new List<int>();
        
        for (int i = 0; i < variables.Length; i++) {
            int a = variables[i][0];
            int b = variables[i][1];
            int c = variables[i][2];
            int m = variables[i][3];
            
            // 计算 (a^b % 10)^c % m
            long firstStep = FastPow(a, b, 10);
            long secondStep = FastPow(firstStep, c, m);
            
            if (secondStep == target) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

var getGoodIndices = function(variables, target) {
    function modPow(base, exp, mod) {
        let result = 1;
        base = base % mod;
        while (exp > 0) {
            if (exp % 2 === 1) {
                result = (result * base) % mod;
            }
            exp = Math.floor(exp / 2);
            base = (base * base) % mod;
        }
        return result;
    }
    
    const result = [];
    
    for (let i = 0; i < variables.length; i++) {
        const [a, b, c, m] = variables[i];
        
        const firstMod = modPow(a, b, 10);
        const secondMod = modPow(firstMod, c, m);
        
        if (secondMod === target) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n × log(max(b, c)))
空间复杂度O(1)

其中 n 是 variables 数组的长度，log(max(b, c)) 是快速幂算法的时间复杂度。