UVA 10692 - Huge Mods

题目链接

题意：求a0a1a2...mod m

思路：直接算肯定不行，利用欧拉定理ab=a(b mod phi(m) + phi(m))(b>=phi(m)),对指数进行降值处理，然后就可以利用快速幂去计算了，计算过程利用递归求解。

代码：

#include <stdio.h>
#include <string.h>

const int N = 1005;
int phi[N * 10], vis[N * 10], m, n, a[N];
char M[15];

int pow_mod(int x, int k, int mod) {
	int now = 1;
	for (int i = 0; i < k; i++) {
		if (x == 1) break;
		now *= x;
		if (now >= mod) break;
 	}
 	if (now >= mod) now = mod;
 	else now = 0;
	if (k == 0) return 1;
	int ans = pow_mod(x * x % mod, k>>1, mod);
	if (k&1) ans = ans * x % mod;
	return ans + now;
}

int dfs(int i, int mod) {
	if (i == n - 1) {
 		if (a[i] >= mod)
   			return a[i] % mod + mod;
      	return a[i];	
	}
	int k = dfs(i + 1, phi[mod]);
	return pow_mod(a[i], k, mod);
}

int main() {
	for (int i = 1; i <= 10000; i++)
		phi[i] = i;
	for (int i = 2; i <= 10000; i++) {
		if (vis[i]) continue;
		for (int j = i; j <= 10000; j += i) {
			phi[j] = phi[j] / i * (i - 1);
			vis[j] = 1;
  		}
 	}
 	int cas = 0;
	while (~scanf("%s", M) && M[0] != '#') {
 		sscanf(M, "%d", &m);
 		scanf("%d", &n);
 		for (int i = 0; i < n; i++)
 			scanf("%d", &a[i]);
 		printf("Case #%d: %d\n", ++cas, dfs(0, m) % m);	
 	}
	return 0;
}