文章目录
  1. 1. 原题
  2. 2. 分析
  3. 3. 快速幂模运算 - 二分法
    1. 3.1. 递归法
    2. 3.2. 非递归法
  4. 4. 解决PE188
    1. 4.1. 递归方法:
    2. 4.2. 非递归方法:
    3. 4.3. 输出
  5. 5. 小结

Project Euler 188 ,求超指数1777↑↑1855的最后8位。Completed on 2013-04-28 11:27

原题

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.

分析

这个数必然是个天文数字,我机器上的整个硬盘也存不下它。求这个数T的最后8位数字,其实就是求T mod 10^8。有一个关于模运算的公式:
(A * B) % M = ( (A % M) * (B % M) )%M
从而:
An % M = (A % M)n % M

快速幂模运算 - 二分法

递归法

实现 np % m 的二分法求模算法如下:

public static long powerMod2(long n, long p, long m) {
if (p == 0) {
return 1;
} else if (p == 1) {
return n % m;
}
long tmp = 1;
tmp = powerMod2(n, p / 2, m);
tmp = tmp * tmp % m;
if ((p & 1) != 0) {
tmp = tmp * n % m;
}
return tmp;
}

解析:

  • 当p为奇数时:
    np%m = (n % m) np-1 % m = r np-1 % m ,此是p-1为偶数;
  • 当p为偶数时:
    np % m = n2k % m = (nk % m )2 % m = tmp * tmp % m
    其中k = p/2,tmp = nk % m = powerMod2(n,k,m)

非递归法

非递归的蒙哥马利(Montgomery)幂模运算:

public static long powerMod(long n, long p, long m) {
long r = n % m;
long tmp = 1;
while (p > 1) {
if ((p & 1) != 0) {// p 是奇数,则
tmp = (tmp * r) % m;
}
r = (r * r) % m;
p >>= 1;
}
return (r * tmp) % m;
}

解决PE188

递归方法:

a↑↑(k+1) % m = (a(a↑↑k)) % m = powMod(a,a↑↑k %m,m)
所以,对于模m的余数,每次用a % m 替换 a,(k+1)就可以降到k。从而得到代码:

static long hyper_exp2(long a, long k, long m) {
if (k == 1) {
return a;
}
return powerMod(a, hyper_exp2(a, k - 1, m), m);
}

非递归方法:

public static void main(String[] args) {
long s = System.nanoTime();
System.out.println(hyper_exp(1777, 1855, 100000000));
System.out.println("time consumed:" + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - s) + " ms");
}
static long hyper_exp(long a, long k, long m) {
long temp = 1;
while (k > 0) {
temp = powerMod(a, temp, m);
k--;
}
return temp;
}

输出

95962097
time consumed:8 ms

小结

参考1-幂取模算法
参考2-
Montgomery算法

文章目录
  1. 1. 原题
  2. 2. 分析
  3. 3. 快速幂模运算 - 二分法
    1. 3.1. 递归法
    2. 3.2. 非递归法
  4. 4. 解决PE188
    1. 4.1. 递归方法:
    2. 4.2. 非递归方法:
    3. 4.3. 输出
  5. 5. 小结