題目連結(jié)：
題目大意：
輸入第一列給定一正整數(shù) t （1 ≦ t ≦ 100000），代表有 t 筆測(cè)試資料，每筆佔(zhàn)一列。每列給定兩整數(shù) a 、 b （0 ≦ a ≦ 2147483647，b 不超過(guò) 700 個(gè)位數(shù)長(zhǎng)），代表有一個(gè)十進(jìn)位的數(shù)字 a 以及一個(gè)八進(jìn)位數(shù)字 b。試問(wèn)十進(jìn)位制下 a ^ b 除以十進(jìn)位數(shù)字 10 ^ 9 + 7 的餘數(shù)為何？
範(fàn)例輸入：
2
3 10
2 15
範(fàn)例輸出：
6561
8192
解題思維：
首先，10 ^ 9 + 7（也就是 1000000007）是一個(gè)質(zhì)數(shù)。接著，有一個(gè)強(qiáng)大的定理叫做
費(fèi)馬小定理（Fermat's Little Theorem）
其內(nèi)容基本上是
a ^ (p - 1) ≡ 1 (mod p)
其中 a 為任意整數(shù)、 p 為一質(zhì)數(shù)且「mod」意旨取餘數(shù)之操作。
而因?yàn)榇畏綌?shù) b 可以很大，再加上我們要求的是取 10 ^ 9 + 7 的餘數(shù)，因此我們可以藉由上面的定理將 b 變小。
可以看到本題中 p = 10 ^ 9 + 7，因此每 p - 1 次方餘數(shù)就會(huì)回到 1 。因此我們實(shí)際上只需要知道 a ^ (b mod (p - 1)) 便可以知道 a ^ b mod p 的餘數(shù)為何。
而不須大數(shù)運(yùn)算便可以求得 b mod (p - 1) 之值，我們只需要利用餘數(shù)的性質(zhì)即可——取餘數(shù)之操作的先後順序不影響同餘性（參見(jiàn)這題）。
最後，計(jì)算 a ^ (b mod (p - 1)) 需要利用快速冪之技巧?？梢詤⒁?jiàn)這題。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
達(dá)人
