主題
題目連結：
題目大意：
輸入第一列給定一正整數 t（1 ≦ t ≦ 1000），代表測試資料筆數，每筆佔一列。每列給定兩正整數 x 、 M（1 ≦ x 、M ≦ 10 ^ 9），試問
之值。其中「mod」為模運算，即除以某數取餘數之行為。
注：上圖中的次方塔（Power tower）在數學中的預設情況，並非由下往上算而是如題目名稱所述是由上至下算。而若使用高德納箭號表示法（Knuth's up-arrow notation）加上極限表示法，則上圖中的式子可以寫成以下
其中的雙重向上箭號即代表重冪運算，即次方塔。
範例輸入：
20
2 8
1 10
10 10
7 5
3 5
8 8
5 10
231228741 865307307
435166813 653746644
128892216 736788461
554621045 505103381
149307601 156938952
779806570 872026572
28504859 366432995
264755358 95190821
53007951 708838043
302568050 942476231
602127323 443381811
731148223 190757658
583517685 297562649
範例輸出：
0
1
0
3
2
0
5
162896679
487156897
197477682
145581417
88566985
452218540
245148199
39125978
137759364
346806201
106008215
100442329
130461966
解題思維：
以前有提及過數論中的歐拉定理（Euler's Theorem），即
x ^ φ(M) ≡ 1 (mod M)
因此 x 的次方值之餘數每 φ(M) 項就會循環一次。例如 7 的次方項 mod 10 會有長度為 φ(10) = 4 的循環節：
7 ^ 1 ≡ 7 (mod 10)
7 ^ 2 ≡ 9 (mod 10)
7 ^ 3 ≡ 3 (mod 10)
7 ^ 4 ≡ 1 (mod 10)
7 ^ 5 ≡ 7 (mod 10)
……
注：這個定理保證每 φ(M) 項必定循環，並不代表「最短」循環節就是 φ(M)。例如當 x = 1 時，每一個次方項都是同餘，此時最短循環節為 1。
因此題目的次方塔便可以改寫成下式
可以看到我們將會有下列子問題（因為次方塔是由上至下算）
而其可以根據同樣的論述寫成以下形式（即把 φ(M) 當作「新的」M 值）
以此類推。直到最後的「M」變成 1 為止，此時可以看到不論什麼數字 mod 1 都是 0，因此便可以回頭算出答案。
例如說當 x = 7、M = 10 時，會得出：
的結論，其中 φ(10) = 4 、 φ(4) = 2 、 φ(2) = 1。所以模（mod）1 的那一層結果為 0，因此上式變為
而 7 ^ 0 = 1，模 2 之後的值為 1。因此得到
而 7 ^ 1 = 7，模 4 之後的值為 3。所以得
因此最終結果為 3。
而過程中有出現 7 ^ 0 、 7 ^ 1 、 7 ^ 3，雖然這個例子中很小，但是有可能會出現 31506 ^ 48763 等指數部分很大之數字。此時可以使用快速冪來求出數值，很久以前的文章之中間部分有介紹原理。
那關鍵的歐拉計數函數 φ(M) 怎麼求呢？首先，把 M 因數分解（分解方式可以參見這題）成
其中 p1 、 p2 等是質數。則 φ(M) 即為
以上是本題的基本架構。但是很不幸地，上述結論不一定是「對的」。
回到一開始的歐拉定理，該定理有一個條件才能成立——也就是 x 和 M 要互質（兩者最大公因數為 1）。如果不互質怎麼辦？此時仿造計算 φ(M) 時的作法，我們先把 M 值因數分解成
然後把次方塔改寫成下列方程組
其中每個求出 r1 、 r2 等分別各自是一個子問題。所以可以套用先前的結論，但是有可能會繼續遇到不互質的問題（所以又要回到這邊的結論）。而當中會出現 x 與某個質數 pi 的最大公因數不為 1（否則就可以使用一開始的結論，因為兩者互質），此時 ri 即為 0。
而當每個子問題各自遞迴地解完便得到了 r1 、 r2 等之值。最後利用中國剩餘定理（Chinese Remainder Theorem）便可以得到結果為
其中
也就是 Mi 之值為 M 除掉 pi 這個質因數後的樣子，並且其滿足
也代表著 ti 為 Mi 模 pi ^ ci 下的模反元素（Modular Inverse，求法可以參見這題）。
以上這樣子才算是補全了結論。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
