当前位置:首页 » Project Euler » 详细页

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.

Solution

按照题目要求模拟,但需要一些技巧: 考虑 $$ ^{k+1}a= a^{ ^{k}a}$$ 结果需要对$10^8$取模,所以考虑一般情况对$p$取模 $$ ^{k+1}a\ mod \ p \quad = \quad a^{ ^{k}a}\ mod \ p \quad = \quad \left( a^x\ mod\ p\right) ^y \times a^z\ mod\ p$$ 上式中$xy+z= ^{k}a,\quad z< x, \quad a^x\ mod\ p=1$,则显然有$z=^{k}a \ mod\ x$ 只需要找到最小的$x$使得$a^x\ mod\ p=1$即可大大优化效率。

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