【题解】Huge Mods UVa 10692 欧拉定理

题意：计算a1^( a2^( a3^( a4^( a5^(...) ) ) ) ) % m的值，输入a数组和m，不保证m是质数，不保证互质

裸的欧拉定理题目，考的就一个公式 a^b = a^( b % phi(m) + phi(m) ) ( mod m )，这个公式的前提条件是 b >= phi(m)

但是这道题并不需要判断b >= phi(m)的条件，直接用公式就能过掉，而且udebug的标程也是错的

而且我也不知道像这样的形式如何判断b >= phi(m)，如果有神犇会的话欢迎教教本蒟蒻

一组叉掉std和我的程序的数据：8 2 6 2，答案是4，程序输出0。

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <utility>
 6 
 7 using namespace std;
 8 const int MAXN = 11;
 9 
10 int m, n, a[MAXN];
11 
12 int phi( int x ) {
13     int ans = x;
14     for( int i = 2; i*i <= x; ++i )
15         if( x % i == 0 ) {
16             ans = ans / i * (i-1);
17             while( x % i == 0 ) x /= i;
18         }
19     if( x > 1 ) ans = ans / x * (x-1);
20     return ans;
21 }
22 int pow_mod( int a, int b, int m ) {
23     if( !b ) return 1;
24     int rtn = pow_mod(a,b/2,m);
25     rtn = rtn * rtn % m;
26     if( b&1 ) rtn = rtn * a % m;
27     return rtn;
28 }
29 
30 int solve( int i, int mod ) {
31     if( i == n-1 ) return a[i] % mod;
32     int b = solve( i+1, phi(mod) ); // 这里没有判断b >= phi(mod)，直接就过掉了
33     return pow_mod( a[i], b+phi(mod), mod );
34 }
35 
36 int main() {
37     int kase = 1;
38     while( scanf( "%d", &m ) == 1 ) {
39         scanf( "%d", &n );
40         for( int i = 0; i < n; ++i ) scanf( "%d", a+i );
41         printf( "Case #%d: %d
", kase++, solve(0,m) );
42     }
43     return 0;
44 }