双模幂运算

难度: Medium

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [a_i, b_i, c_i, m_i]，以及一个整数 target 。

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

0 <= i < variables.length
((a_i^b_i % 10)^c_i) % m_i == 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³ % 10)³ % 10 = 2 。
2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(3³ % 10)³ % 1 = 0 。
3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(6¹ % 10)¹ % 4 = 2 。
因此，返回 [0,2] 作为答案。

示例 2：

输入：variables = [[39,3,1000,1000]], target = 17
输出：[]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(39³ % 10)¹⁰⁰⁰ % 1000 = 1 。
因此，返回 [] 作为答案。

提示：

1 <= variables.length <= 100
variables[i] == [a_i, b_i, c_i, m_i]
1 <= a_i, b_i, c_i, m_i <= 10³
0 <= target <= 10³

Submission

运行时间: 21 ms

内存: 16.1 MB

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        ans=[]
        for i,(a,b,c,d) in enumerate(variables):
            if ((a**b%10)**c)%d==target:
                ans+=[i]
        return ans

Explain

对于每个元素 [ai, bi, ci, mi]，首先计算 a^b 的最后一位数字，这是通过 a^b % 10 实现的。接下来，计算这个结果的 ci 次幂，然后取模 mi，即 ((a^b % 10)^c) % mi。如果这个结果等于 target，那么这个索引 i 就是一个好下标。算法对每个元素进行此操作，并将所有好下标收集到结果列表中。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        ans = []  # 结果列表，用来存储好下标
        for i, (a, b, c, d) in enumerate(variables):  # 遍历 variables 数组
            # 计算 ((a^b % 10)^c) % d 并检查是否等于 target
            if ((a**b % 10)**c) % d == target:
                ans.append(i)  # 如果是好下标，添加到结果列表
        return ans  # 返回好下标的列表

Explore

在计算 a^b 时，如果 b 非常大，直接计算 a^b 可能会导致非常大的数值，这不仅增加了计算的复杂性，也可能导致计算机无法处理如此大的数字（即溢出）。通过首先计算 a^b % 10，我们实际上是在利用模运算的性质，即 (x^y) % z = ((x % z)^y) % z，来减少计算量并避免处理大数。这样我们只需关心最后一位数的幂运算，从而简化了问题和计算过程。

是的，b 或 c 的值如果非常大，直接进行幂运算可能会导致数值溢出，特别是在不进行任何模运算的情况下。这就是为什么在题解中使用了模运算来处理 a^b 和 ((a^b % 10)^c) 的计算，通过模运算可以有效地降低结果的数值范围，避免溢出。此外，使用模运算也可以保持计算结果在一个可管理的数值范围内，从而防止运算过程中的资源耗尽。

快速幂算法是一种高效的计算 x^n 的方法，特别是当 n 很大时。它通过将幂运算分解成更小的部分，利用迭代的方法减少乘法的次数。在题解中，确实可以考虑使用快速幂来优化幂运算的过程，特别是当 b 和 c 的值很大时。通过快速幂，我们可以在对数时间复杂度内完成幂运算，这将显著提高算法的效率和处理大规模数据的能力。

确实，没有处理特殊的边界情况可能会影响算法的鲁棒性。例如，如果输入数组为空，算法应该返回一个空的结果列表而不是产生错误。同样，对于极大的数值，算法应该能够正确处理或至少提供明确的错误消息。在实际应用中，应当在算法的开始阶段添加对输入数据的验证，确保输入数据在预期范围内，并且处理任何异常情况，以保证算法的稳定性和可靠性。