我如何计算以 m 为模的主要电力塔

Question

问题来了——我得到了一个质数 P 和一个数 K。我需要计算 P ^ P ^ P ... k 次模到 m。

这里P是素数。

(P ^ (P ^ (P ^ P .... k times))) % m

几个例子

对于 P = 2, K = 3, m = 3

2 ^ 2 ^ 2 % 3 = 1

对于 P = 5，K = 3，m = 3

5 ^ 5 ^ 5 % 3 = 2

我可以使用蛮力，但问题是数字会变得非常大。

这是限制条件

2 <= p < 10 ^ 8
1 <= k < 10 ^ 8 
1 <= m <= 10 ^ 8

Answer 1

假设求幂是左关联的，这意味着您必须计算：

[(p^p)^p]^p ... k times

注意：如果这是一个错误的假设，那么您的问题是这个问题的重复。事实上，你的更容易，因为p是质数。

那么这等于：

p^(p*p*p*... k times)

这等于：

p^(p^k)

通过平方来使用指数是可行的O(log p^k) = O(k log p)

但是，这对于您规定的限制来说仍然太多了p, k < 10^8。

为了使它更好，您可以使用Douglas Zare的答案中的一些信息：

你可以说 a^k mod m = a^(k mod phi(m)) mod m。然而，当 a 和 m 不互质时，情况并非总是如此

幸运的是，a = p在我们的例子中， 和p是素数，所以这成立。

所以你的问题归结为计算：

p^(p^k mod phi(m)) mod m

需要通过平方进行两次求幂，这很容易实现。

了解如何有效计算 totient 函数：

int phi(int n)
{    
    int result = n;   // Initialize result as n

    // Consider all prime factors of n and subtract their
    // multiples from result
    for (int p=2; p*p<=n; ++p)
    {
        // Check if p is a prime factor.
        if (n % p == 0)
        {
            // If yes, then update n and result 
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }

    // If n has a prime factor greater than sqrt(n)
    // (There can be at-most one such prime factor)
    if (n > 1)
        result -= result / n;
    return result;
}