【高次べき乗型取りの応用】HDU 3609 Up-up

KIDxの問題を解く報告のテーマはとても分かりやすいです:http://acm.hdu.edu.cn/showproblem.php?pid=3609はべき乗の公式を下げます:このスピードは前の10まで並ぶことができます:

#include <iostream>
using namespace std;
#define LL unsigned __int64
#define M 205

int phi[M];

int Euler (int n)    // n    
{
	int i, res = n;
	for (i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			res = res - res/i;
			while (n % i == 0)
				n /= i;
		}
	}
	if (n > 1)
		res = res - res/n;
	return res;
}

LL qmod (LL a, LL b, int c)    //     
{
	LL res = 1;
	for ( ; b; b >>= 1)
	{
		if (b & 1)
			res = res * a % c;
		a = a * a % c;
	}
	return res;
}

LL isok (LL a, LL b, int c)    //     a^b  >=c
{
	LL res = 1, i;
	for (i = 0; i < b; i++)
	{
		res *= a;
		if (res >= c)
			return res;
	}
	return res;
}

LL upup (LL a, int k, int num)    //           
{
	if (phi[num] == 1) return 1;    //        ，         1，       
	if (k == 1) return a % phi[num];//      a  
	LL b = upup (a, k-1, num+1);    //  a  b
	LL x = isok (a, b, phi[num]);
	if (x >= phi[num])    //       ，          ，      a  
		return qmod (a % phi[num], b, phi[num]) + phi[num];
	else return x;    //     ，    a^b，     a  
}

int main()
{
	LL a;
	int k;
	phi[0] = 100000000;
	for (k = 1; k < M; k++)
		phi[k] = Euler (phi[k-1]);    //        
	while (~scanf ("%I64u%d", &a, &k))
	{
		printf ("%I64u
", upup (a, k, 0) % phi[0]);
	}
    return 0;
}