🔗 🟡 2961. Double Modular Exponentiation 1451

tags: `Weekly Contest 375` `陣列(Array)` `數學(Math)` `模擬(Simulation)`

題意

給定一個二維陣列 $variables$ ，其中 $variables[i] = [a_i, b_i, c_i, m_i]$ ，以及一個整數 $target$ 。求滿足 $((a_i^{b_i} \mod 10)^{c_i} \mod m_i) = target$ 的 $i$ 的集合，以陣列的方式返回，順序不限。

約束條件

$1 \leq variables.length \leq 100$
$variables[i] = [a_i, b_i, c_i, m_i]$
$0 \leq a_i, b_i, c_i, m_i \leq 10^3$
$0 \leq target \leq 10^3$

思路：使用快速冪模擬

對於每個 $i$ ，計算 $((a_i^{b_i} \mod 10)^{c_i} \mod m_i)$ ，如果計算結果等於 $target$ ，則將下標 $i$ 加入答案陣列中。

而計算 $pow(a, b, m)$ 可以使用快速冪(平方求冪) 計算，時間複雜度 $O(\log b)$ 。

在 python 中，內建的 pow 函數已經內置了快速冪，直接使用即可，其他語言需要自己實現。

複雜度分析

時間複雜度 $O(n \log U)$ ，其中 $n$ 為 $variables$ 的長度， $U$ 為 $b_i, c_i$ 的最大值，本題中最大值為 $10^3$ 。
空間複雜度 $O(1)$ ，不考慮答案的空間複雜度。

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        ans = []
        for i, (a, b, c, m) in enumerate(variables):
            if pow(pow(a, b, 10), c, m) == target:
                ans.append(i)
        return ans

class Solution {
public:
    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
        int n = variables.size();
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int a = variables[i][0], b = variables[i][1], c = variables[i][2], m = variables[i][3];
            if (my_pow(my_pow(a, b, 10), c, m) == target) {
                ans.push_back(i);
            }
        }
        return ans;
    }
    int my_pow(int a, int b, int m) {
        int ans = 1;
        while (b) {
            if (b & 1) {
                ans = (ans * a) % m;
            }
            a = (a * a) % m;
            b >>= 1;
        }
        return ans;
    }
};