the
operator for exponentiation is different from the addition, subtraction,
multiplication or division operators in the sense that the default associativity
for exponentiation goes right to left instead of left to right. so unless we
mess it up by placing parenthesis,
should mean
not
. this leads to the
obvious fact that if we take the levels of exponents higher (i.e., 2^3^4^5^3),
the numbers can become quite big. but let‘s not make life miserable. we being
the good guys would force the ultimate value to be no more than 10000.
given a1, a2, a3, ... ,
an and m(=10000)
you only need to compute
a1^a2^a3^...^an mod m.
there
can be multiple (not more than 100) test cases. each test case will be presented
in a single line. the first line of each test case would contain the value for
m(2<=m<=10000). the next number of that line would be n(1<=n<=10).
then n numbers - the values for a1,
a2,
a3,
... , an would
follow. you can safely assume that 1<=ai<=1000.
the end of input is marked by a line containing a single hash (‘#‘) mark.
for
each of the test cases, print the test case number followed by the value of
a1^a2^a3^...^an mod
m on one line. the sample output shows the exact format for printing the test
case number.
題意：求出 a0^a1^a2......a^n%m的值。
sl: 以前做過一個a^b mod 1e9+7 的題，那個很顯然是費馬小定理。碰見這個題目傻逼了。
百度學習一翻知：a^x=a^(x%phi[[m]+phi[m]) (phi[m]<=x) 很顯然一個遞歸的式子。
哎，但是當時每次都是對x%phi[mod] 傻叉了。應該遞歸求解。
坑了我4個點真吭。。。