前往
大廳
主題

LeetCode - 2961. Double Modular Exponentiation 解題心得

Not In My Back Yard | 2025-01-27 12:00:01 | 巴幣 2 | 人氣 30

題目連結:


題目意譯:
你被給定一個索引值從 0 開始數的二維陣列 variables,其中 variables[i] = [ai, bi, ci, mi]。同時你被給定另一個整數 target。

一個索引值 i 是「好的」,代表著以下公式成立:
    0 ≦ i < variables.length
    ((ai ^ bi % 10) ^ ci) % mi == target

回傳一個陣列包含著所有的好索引值。順序任意。

限制:
1 ≦ variables.length ≦ 100
variables[i] == [ai, bi, ci, mi]
1 ≦ ai, bi, ci, mi ≦ 10 ^ 3
0 ≦ target ≦ 10 ^ 3



範例測資:
範例 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。
因此我們回傳 [] 作為答案。


解題思維:
一樣使用快速冪來計算次方值(與其模運算之結果)即可,如這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
追蹤 創作集

作者相關創作

更多創作