题目描述： 大家对指数运算都非常熟悉，定义f(n,k) = n ^ k （n的k次方）， 例如f(2, 3) = 8, f(3,4) = 81。 我们定义f(0,0) = 1。 我们的目标是给定整数n1,k1,n2,k2,n，求f(f(n1,k1),f(n2,k2)) % n。 
(％是取余数运算)。 输入格式 多组数据，每组数据就一行包含5个整数n1,k1,n2,k2,n。
0<=n1,k1,n2,k2<=1000000000, 1 <= n <=10000000) 输出格式 每组数据一行，表示最终结果。 
挑战规则： 
输入样例   1 2 3 4 5 5 4 3 2 1 输出样例   1 0 解决思路： 首先理清解题方向 f(f(n1,k1),f(n2,k2))%n  => (n1^k1)^(n2^k2)%n => n1^(k1*n2^k2)%n 注意：(n1^k1)^(n2^k2) != n1^k1^n2^k2 下面主要考虑f(f(n1,k1),f(n2,k2)) > n的情况： 1.求出n1^m%n的所有可能值，并保存； 2.求出(k1*n2^k2)对于步骤1结果的个数的取余k； 3.返回1中的第k个值，如果k为0，取最后一个。 下面是具体实现，本人测过一些，都是可以的，由于csdn答题框老是加载不出来，所以请大家帮忙验证一下！ /****************************************************/ // 模取幂运算 计算a^b mod c // 利用公式 // (a*b)mod(c) = ((a mod c )*b mod c /****************************************************/ int a_b_Mod_c(int a, int b, int c) {//前提 a b c 都是正数 int digit[32]; int i, k; long long resualt = 1; i = 0; while(b)//把b化成2进制 { digit[i++] = b%2; b >>= 1; } //计算(a^b) mod c for(k = i-1; k >= 0; k--) { resualt = (resualt * resualt) % c; if(digit[k] == 1) { resualt = (resualt * a) % c; } } return resualt; } //计算(b*n^k)%mod int fmod(int n, int k, int mod, int b) { long long res; if (mod < 2) return 0; res = a_b_Mod_c(n,k,mod); return (res*b)%mod; } //find all numbers n^m%mod can be int findAll(int n, int mod) { int tm = n%mod; int first = tm; long tmp = tm; int i = 1; while(1) { tmp *= tm; if (tmp > mod) { tmp = tmp%mod; if (tmp == first) break; } i++; } printf("all %d ", i); return i; } //check if (n^k)^(n1^k1)is big than to, if not return (n^k)^(n1^k1),else return 0 int bigOrMod(int n, int k, int n1, int k1, int to) { int i,j,t; long m; m = 1; for (i = 0; i < k; i++) { m *= n; if (m > to) return 0; } t = m; m = 1; for (i = 0; i < k1; i++) { for(j = 0;j < n1; j++) { m *= t; if (m > to) return 0; } } printf("%d->(%d,%d,%d):%ld ", n, k, n1, k1, m); return m; } int fffmod(int n, int k, int n1,int k1, int mod) { int i,tmp,all; long result = 1; if (mod < 2) return 0; if (!(n1&&k1))//if n1 or k1 is 0,n1^k1 will 1,don't need return fmod(n,k,mod,1); if (!(n&&k) || 1==n)//if n or k is 0,f(f(n,k),f(n1,k1)) will equal to 1 return 1; if ((tmp = bigOrMod(n,k,n1,k1,mod))!= 0) return tmp; else { printf("findall "); all = findAll(n, mod); printf("fmod "); tmp = fmod(n1, k1, all, k); tmp = tmp?tmp:all; printf("result "); result = a_b_Mod_c(n, tmp, mod); } return result; }