主題

ZeroJudge - f729: 大數冪 解題心得

Not In My Back Yard | 2021-04-15 02:34:00 | 巴幣 0 | 人氣 68

題目連結:


題目大意:
輸入第一列給定一正整數 t (1 ≦ t ≦ 100000),代表有 t 筆測試資料,每筆佔一列。每列給定兩整數 a 、 b (0 ≦ a ≦ 2147483647,b 不超過 700 個位數長),代表有一個十進位的數字 a 以及一個八進位數字 b。試問十進位制下 a ^ b 除以十進位數字 10 ^ 9 + 7 的餘數為何?



範例輸入:
2
3 10
2 15


範例輸出:
6561
8192


解題思維:
首先,10 ^ 9 + 7(也就是 1000000007)是一個質數。接著,有一個強大的定理叫做
費馬小定理(Fermat's Little Theorem)
其內容基本上是
a ^ (p - 1) ≡ 1 (mod p)
其中 a 為任意整數、 p 為一質數且「mod」意旨取餘數之操作。

而因為次方數 b 可以很大,再加上我們要求的是取 10 ^ 9 + 7 的餘數,因此我們可以藉由上面的定理將 b 變小。

可以看到本題中 p = 10 ^ 9 + 7,因此每 p - 1 次方餘數就會回到 1 。因此我們實際上只需要知道 a ^ (b mod (p - 1)) 便可以知道 a ^ b mod p 的餘數為何。

而不須大數運算便可以求得 b mod (p - 1) 之值,我們只需要利用餘數的性質即可——取餘數之操作的先後順序不影響同餘性(參見這題)。

最後,計算 a ^ (b mod (p - 1)) 需要利用快速冪之技巧。可以參見這題




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

創作回應

相關創作

更多創作