How do I solve Fredo and Maths problem? I have seen the Editorial but could not catch the way of using Totient Function.
1 Like
Lets represent the expression x^x^…k times as f(x,k), so, we need to find f(x,k)%m its given that ‘x’ is always a prime and m < x, so gcd of (m,x) will be equal to 1, and we can use Fermat’s little theorem. One other thing that you need to see is that f(x,k)%m = (x^f(x,k-1))%m, but due to Fermat’s theorem, (x^f(x,k-1))%m = (x^(f(x,k-1)%phi(m)))%m, now our problem reduces to finding f(x,k-1)%phi(m) and raising ‘x’ to that power. But we can apply Fermat’s theorem again, to evaluate this new expression, because, f(x,k-1) = x^(f(x,k-2)) so,
f(x,k-1)%phi(m) = (x^(f(x,k-2)))%phi(m) = (x^(f(x,k-2)%phi(phi(m))))%phi(m), by repeatedly applying this, you will reach a point where you have to evaluate some f(x,k-l)%phi(phi(…l times…phi(n))). One property of the totient function is that if you keep applying it repeatedly to the some number, say ‘n’, it reaches 1, and it takes O(Log N) repetitions to reach there (Log M times in this problem), So you will simply return zero at that point because any number modulo 1 is zero. Have a look at my submission :
https://www.hackerearth.com/submission/8263493/
Let me know (comment) if there is something you didn’t understand.
3 Likes
Can you elaborate how did you use fermat’s little theorem here? I mean how could you managed to break the power of powers by using that?
Sorry for the late reply. Like I said, you recursively keep reducing the number of terms and M (by applying Fermat’s theorem, reducing the size, and repeating again), at some point M will reach 1, and it doesn’t matter how many terms are left because anything modulo 1 will be zero. You will understand this better if you write it down on a paper, and then see what you actually need to find (that is what I did when I tried to solve this)
1 Like