对于 a、b、m 的较大值，我必须有效地计算 a^^b mod m<2^32
其中 ^^ 是四分运算符： 2^^4=2^(2^(2^2))
m 不是素数，也不是 10 的幂。
你能帮忙吗？
需要明确的是，a^^b 和 a^b 不是一回事，它是指数塔 a^(a^(a^...^a))，其中有 b 个 a 副本，也称为四分法。令 T(a,b) = a^^b 因此 T(a,1) = a 且 T(a,b) = a^T(a,b-1)。
为了计算 T(a,b) mod m = a^T(a,b-1) mod m，我们需要计算具有极大指数的 mod m 的幂。您可以使用的是，模幂是前周期的，前周期长度最多为 m 素数分解中素数的最大幂，即最多 log_2 m，并且周期长度除以 phi(m)，其中 phi(m)是欧拉 totient 函数。事实上，周期长度除以 m 的Carmichael 函数，即 lambda(m)。所以，
a^k mod m = a^(k+phi(m)) mod m as long as k>log_2 m.
请注意，a 不一定与 m（或以后与 phi(m)、phi(phi(m)) 等）互质。如果是，您可以说 a^k mod m = a^(k mod phi(m)) mod m。然而，当 a 和 m 不互质时，情况并非总是如此。例如，phi(100) = 40，2^1 mod 100 = 2，但 2^41 mod 100 = 52。您可以将大指数减少到至少为 log_2 m 的同余数 mod phi(m)，因此您可以说 2^10001 mod 100 = 2^41 mod 100 但你不能将其减少到 2^1 mod 100。你可以定义 mod m [minimum x] 或使用 min + mod(a-min,m)只要a>分钟。
如果 T(a,b-1) > [log_2 m]，则
a^T(a,b-1) mod m = a^(T(a,b-1) mod phi(m) [minimum [log_2 m]])
否则只需计算 a^T(a,b-1) mod m。
递归计算这个。您可以将 phi(m) 替换为 lambda(m)。
计算 2^32 以下数字的素因数分解并不需要很长时间，因为您最多可以在 2^16 = 65,536 次试除中确定素因数。像 phi 和 lambda 这样的数论函数很容易用素因数分解来表达。
在每一步中，您都需要能够计算小指数的模幂。
您最终会计算 power mod phi(m)，然后 powers mod phi(phi(m))，然后 powers mod phi(phi(phi(m)))，等等。在迭代之前不需要那么多迭代phi 函数为 1，这意味着您将所有内容减少到 0，并且您不再通过增加塔的高度来获得任何变化。
这是一个高中数学竞赛中包含的类型的示例，参赛者应该重新发现这一点并手动执行它。 14^^2016 的最后两位数是多少？
14^^2016 mod 100
= 14^T(14,2015) mod 100
= 14^(T(14,2015) mod lambda(100) [minimum 6]) mod 100
= 14^(T(14,2015 mod 20 [minimum 6]) mod 100
T(14,2015) mod 20
= 14^T(14,2014) mod 20
= 14^(T(14,2014) mod 4 [minimum 4]) mod 20
T(14,2014) mod 4
= 14^T(14,2013) mod 4
= 14^(T(14,2013 mod 2 [minimum 2]) mod 4
T(14,2013) mod 2
= 14^T(14,2012) mod 2
= 14^(T(14,2012 mod 1 [minimum 1]) mod 2
= 14^(1) mod 2
= 14 mod 2
= 0
T(14,2014) mod 4
= 14^(0 mod 2 [minimum 2]) mod 4
= 14^2 mod 4
= 0
T(14,2015) mod 20
= 14^(0 mod 4 [minimum 4]) mod 20
= 14^4 mod 20
= 16
T(14,2016) mod 100
= 14^(16 mod 20 [minimum 6]) mod 100
= 14^16 mod 100
= 36
所以，14^14^14^...^14 以数字 ...36 结尾。
我在理解已接受的答案方面遇到了一些困难，Kaveh 链接的另一个堆栈溢出问题有所帮助。
完整的解决方案使用了多种想法：
为任何寻求更清晰的人添加完全简化的工作 Rust 实现：
fn phi(mut x: u64) -> u64 {
let mut c = 2;
let mut s = x;
while x > 1 {
if x % c == 0 {
s -= s / c;
}
while x % c == 0 {
x /= c;
}
c += 1;
}
s
}
fn mod_exp(b: u64, p: u64, m: u64) -> u64 {
if p == 0 {
1
} else if p & 1 == 1 {
(b * mod_exp(b, p - 1, m)) % m
} else {
mod_exp((b * b) % m, p >> 1, m)
}
}
fn mod_tetr(b: u64, p: u64, m: u64) -> u64 {
if b % m == 0 {
0
} else if p == 1 {
b
} else {
mod_exp(b, phi(m) + mod_tetr(b, p - 1, phi(m)), m)
}
}
这是使用 https://stackoverflow.com/a/75399161/22471833 的简单 C# 解决方案。使用下一个输入数据在 Codewars 中进行测试：1 <= base < 1e20, 0 <= height < 1e20, 1 <= modulus < 1e7.
using System.Linq;
using System.Numerics;
using System.Collections.Generic;
public static BigInteger ModTetr(BigInteger b, BigInteger h, BigInteger m)
{
if (m == 1 || b % m == 0)
return 0;
if (b == 1 || h == 0)
return 1;
if (h == 1)
return b % m;
if (b < 3 && h < 5)
return new int[(int)(h - 1)].Aggregate(b, (acc, nxt) => BigInteger.Pow(b, (int)acc)) % m;
return ModExp(b, Phi(m) + ModTetr(b, h - 1, Phi(m)), m);
}
public static BigInteger ModExp(BigInteger b, BigInteger h, BigInteger m)
{
if (h == 0)
return 1;
else if (h % 2 == 0)
return ModExp(b * b % m, h / 2, m);
else
return b * ModExp(b, h - 1, m) % m;
}
public static IEnumerable<BigInteger> Factors(BigInteger n)
{
int d = 2;
while (n != 1)
{
while (n % d == 0)
{
yield return d;
n /= d;
}
d++;
}
}
public static BigInteger Phi(BigInteger n) => Factors(n).GroupBy(x => x).Aggregate(n, (phi, prime) => phi * (prime.Key - 1) / prime.Key);