Как вычислить основную мощность башни по модулю m

Предполагая, что возведение в степень ассоциативно слева, это означает, что вам нужно вычислить:

[(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.

Чтобы сделать его лучше, вы можете использовать некоторую информацию из этого ответа Дуглас Зар:

можно сказать, что 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;
}