1324 . 指數之謎 Exponent
TopCoder
Tags
Description
上個星期，大頭蕃學到了一個新的數論定理：費馬小定理。
大意是說，當P是質數的時候，任何整數X的P-1次方除以P的餘數都會等於1。
大頭蕃覺得太奇妙了！怎能如此神奇，於是他跑去找達克奈特討論這件事情。
經過了一陣雞同鴨講之後，不管大頭蕃說了什麼，達克奈特總是回應「ku ku ku...」，好像某部軍曹動畫裡面帶著螺旋眼鏡的那隻喜歡發出的聲音。
這可讓大頭蕃傷腦筋了，突然，他想到，把這個問題變成程式解題的問題，說不定達克奈特就會回應了！
於是大頭蕃就把它改成了這麼一道題目：
給你m個正整數 X1, X2, ..., Xm，以及k。
請你計算
可是這個題目困擾了大頭蕃好久好久，最後他嘆了一口氣，放棄了。
你能夠幫個忙嗎？
Input Format
輸入檔可能包含多筆測試資料，每一筆佔一列，第一個數字是m，然後有m個數字是X1, X2, ..., Xm，最後是k。(1<=m<=500,000，1<=Xi<231，1<=k<=1,000,000)。
當你發現m=0的時候代表輸入結束。
此外，同一個檔案裡的所有m的總和不超過500,000，並且全部的輸入檔大小總和不超過 5 MB。
Output Format
對於每一筆測試資料，請輸出所求的答案。
Sample Input 1
3 5 4 3 1234
0
0
Sample Output 1
421
Hints
2019/02/28 測資修復 by adrien1018
Problem Source
原TIOJ1324 / TIOJ IOI Warmup III, 2008. Problemsetter: tmt514
EXTREME version of ACM 10692
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |