题目链接：uva 10692 - Huge Mods

题目大意：给出一个数的次方形式，就它模掉M的值。

解题思路：根据剩余系的性质，最后一定是行成周期的，所以就有ab=abmod(phi[M])+phi[M](phi[M]为M的欧拉函数)，这样就可以根据递归去求解。

#include 
   
     #include 
    
      #include 
     
       const int maxn = 15; int A[maxn], k; int pow_mod (int a, int n, int M) { int ans = 1; while (n) { if (n&1) ans = ans * a % M; a = a * a % M; n /= 2; } return ans; } int euler_phi(int n) { int m = (int)sqrt(n+0.5); int ans = n; for (int i = 2; i <= m; i++) { if (n % i == 0) { ans = ans / i * (i-1); while (n%i==0) n /= i; } } if (n > 1) ans = ans / n * (n - 1); return ans; } int solve (int d, int M) { if (d == k - 1) return A[d]%M; int phi = euler_phi(M); int c = solve (d+1, phi) + phi; return pow_mod(A[d], c, M); } int main () { int cas = 1; char str[maxn]; while (scanf("%s", str) == 1 && strcmp(str, "#")) { int M; sscanf(str, "%d", &M); scanf("%d", &k); for (int i = 0; i < k; i++) scanf("%d", &A[i]); printf("Case #%d: %d\n", cas++, solve(0, M)); } return 0; }