Power Tower Modulo — Solution & Editorial

Back to the Problem

Recurse on the exponent modulo φ(M) using Euler's generalized theorem a^e ≡ a^{(e mod φ(m)) + φ(m)} (mod m), valid when e ≥ φ(m). Crucially, only add φ when the true tower above actually reaches φ; a short tower must be used exactly.

Complexity: O(K · √M)

Watch out: Do NOT always add φ: when the exponent tower is smaller than φ(m) (e.g. 2^2 mod 1000 = 4), adding φ gives the wrong residue. Test tower height explicitly.