How can I calculate the main power tower modulo m
Here's the problem - I was given a prime number P and a number K. I need to calculate P ^ P ^ P ... k times modulo m.
Here P is a prime number.
(P ^ (P ^ (P ^ P .... k times))) % m
A few examples
for P = 2, K = 3, m = 3
2 ^ 2 ^ 2 % 3 = 1
for P = 5, K = 3, m = 3
5 ^ 5 ^ 5 % 3 = 2
I can do brute force, but the problem is the numbers can get really big.
here are the contraindications
2 <= p < 10 ^ 8
1 <= k < 10 ^ 8
1 <= m <= 10 ^ 8
source to share
Assuming exponentiation is left associative, which means you should compute:
[(p^p)^p]^p ... k times
Note: if this is a wrong assumption, then your question is a duplicate of this question . In fact, yours is simpler because it p
is simple.
Then it is equal to:
p^(p*p*p*... k times)
What is equal:
p^(p^k)
Using the square elevation , this is doable inO(log p^k) = O(k log p)
But this is too much for your stated limits p, k < 10^8
.
To do it better, you can use some information from this Douglas Zare :
you could say a ^ k mod m = a ^ (k mod phi (m)) mod m. However, this is not always true when a and m are not coprime.
Fortunately, a = p
in our case, a p
is simple, so it takes place.
So, your task comes down to calculations:
p^(p^k mod phi(m)) mod m
It takes two squares, which is easy to do.
See how to evaluate the totient function efficiently :
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;
}
source to share