求10的一億次方對較小整數p取余的餘數？

---

問題泛化的版本：求 。

1) b = 10

直接算。

2) b = 10^10，即本題。

可以用 @小於0 答案中快速冪的方法算。即利用 逐次減半，複雜度O(log b)。

3) b = 10^(10^10), c是素數，ac互質

可以用 @Richard Xu 的費馬小定理做。由於ac互質，根據費馬小定理有。於是就可以用代替b，然後用解法1)或2)搞定。

本質上，費馬小定理就是直接給出了 @冒泡 答案中循環節的長度（前提是c是素數且ac互質），是c-1。

4) b不變，ac互質但c不需要是素數

歐拉定理是費馬小定理的推廣。它指出，在ac互質時，循環節的長度是歐拉函數，即小於等於c的正整數中與c互質的數的個數。

5) b不變，ac不需要互質

若ac不互質，則歐拉定理的條件不滿足。此時，循環節的長度實際上是的某個因數（為什麼？想想gcd(a,c)），於是作為一個更『松』的循環節長度仍然適用。然而，此時的循環是一個『ρ型循環』，或者換句話說，進入循環節之前有一段長度不超過的『不屬於循環的垃圾數據』。那麼，我們只要多重複一次循環節就行了——用代替b即可。

6) b = 10^(10^(10^...))

套用解法5)，則問題的關鍵變成了求，也就是變成了『脫了一層』的子問題。遞歸解之即可。

---

當p=2或5的時候，顯然是0……

當p=3的時候，顯然是1……

當p是其他素數的時候，費馬小定理，因為(10,p)=1所以

10^(p-1) mod p = 1

---

費馬小定理可以直接出

更一般的想法其實是小學的找規律了，比方說p是7，則10的0,1,2,3,。。。次方模7的值是1,3,2,6,4,5,的一個循環，循環節是6，則求指數部分對6的餘數即可

比如有道題是2^(2^(2^(....^2)))，n個2，求對某數的餘數，就可以逐步縮小問題解決

---

這裡可以利用一個性質：

這個很好證明：設

展開以後除了項其他都是的倍數。

利用這個就很好寫了，演算法就是一個遞歸函數，每次把指數折半。這種方法可以適用更一般的情況。

---

for p in range(1,101): print(pow(10,100000000,p))

---

推薦閱讀：