1324 . 指數之謎 Exponent

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

56.5% (13/23)

Submission's AC Ratio

22.4% (63/281)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 65536 262144 1
1 2500 65536 262144 2
2 2500 65536 262144 3
3 2500 65536 262144 4
4 2500 65536 262144 5
5 2500 65536 262144 6
Submit
Back to Top