---

(3^5004) % 10007  =  3^1  (開始循環)

因此建表 dp[1] ~ dp[5004]   (直接用動態規劃  dp[0]=1,  dp[i] = dp[i-1]*3  )

輸入n，直接查表 dp[n % 5003] 即可  

 

---

很厲害的觀察 σ`∀´)σ，原本寫 Python 一直逾時，這個方法順利過

補充一下，(3^5003) % 10007 = 1，建表 dp[0] ~ dp[5002] (size 5003) 就好，因為 0 <= (n % 5003) <= 5002

 

---

出題者很厲害，測資剛好擋住暴力解。

比起 io 題，是有意思多了。

 

---

補充一下這個循環的現象的名稱：

費馬小定理是數論中的一個定理：假如{\displaystyle a}是一個整數，{\displaystyle p}是一個質數，那麼{\displaystyle a^{p}-a}是p的倍數，可以表示為

{\displaystyle a^{p}\equiv a{\pmod {p}}}

如果a不是p的倍數，這個定理也可以寫成

 

{\displaystyle a^{p-1}\equiv 1{\pmod {p}}}

以上取自於 wiki 。

a272 猥瑣罐頭下樓梯也可以用費馬小定理避開快速幂的運算。

但萬一是 d636. 大爆炸bomb 時同樣方法就會不管用，隨著基底的a 不同，取模後的乘法反元素也不同。

 

---

補充一下這個循環的現象的名稱：

費馬小定理是數論中的一個定理：假如 是一個整數， 是一個質數，那麼 是p的倍數，可以表示為 

如果a不是p的倍數，這個定理也可以寫成 

以上取自於 wiki 。

a272 猥瑣罐頭下樓梯也可以用費馬小定理避開快速幂的運算。

          但萬一是 d636. 大爆炸bomb 時同樣方法就會不管用，隨著基底的a 不同，取模後的乘法反元素也不同。

          這句有誤，因為 p 是質數，所以必定會形成 10007 的一次循環。

          而費馬小定理的使用需要建立在 p 是質數的前提，所以若 p 不是質數則得回歸到快速幂的方式。

 

 

---

這網站裡有好幾題都可以用循環節的方式來解題，

也包括 hshua 出的題目，

找出循環節是件有趣的事，

建議別把循環節的長度講出來，

讓解題者找找看。