### The hyperexponentiation of a number题号：188 难度： 35 中英对照

The hyperexponentiation or tetration of a number a by a positive integer b, denoted by a↑↑b or ba, is recursively defined by:

a↑↑1 = a,
a↑↑(k+1) = a(a↑↑k).

Thus we have e.g. 3↑↑2 = 33 = 27, hence 3↑↑3 = 327 = 7625597484987 and 3↑↑4 is roughly 103.6383346400240996*10^12.

Find the last 8 digits of 1777↑↑1855.

### Code


public final class p188 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

final static long N = 1777;
final static long POW = 1855;
final static long MOD = 100000000;

static public String run() {
return ""+hexp(N, POW, MOD);
}

// Calculates min p > 0 such that n**p m ==1.
static long cycleSize(long n, long m) {
long num = n;
long i = 1;
for (; num != 1L; i++) {
num = num * n;
num = num % m;
}
return i;
}

// Caclulates hyperexponiantion with modulo arithmetic
static long hexp(long n, long hexp, long mod) {
if (hexp == 1)
return n % mod;
long mod1 = cycleSize(n, mod);
long exp = hexp(n, hexp - 1, mod1);
long num = 1;
for (long i = 0; i < exp; i++) {
num = num * n;
num = num % mod;
}
return num;
}
}
95962097
58ms