지수 탑

지수 탑 (Power Tower) 은 지수의 반복적 표기로, 다음과 같이 정의합니다.

$$ [x_{1}, x_{2}, ..., x_{n}] = x_{1}^{x_{2}^{.^{.^{.^{x_{n}}}}}} = x_{1}^{\left(x_{2}^{\left(.^{.^{.^{x_{n}}}}\right)}\right)} $$
지수 탑을 임의의 자연수로 나눈 나머지를 구하는 방법은 하단의 참고자료 2에서의 별첨처럼, 구하는 방법이 정해져 있습니다.
(정리 중)
오일러의 정리
서로소인 두 자연수 $a$, $n$에 대하여 $$ a^{\phi(n)} \equiv 1 \pmod{n} $$ 이다.
오일러의 정리에서 파생되는 정리로 다음이 있습니다.
임의의 두 자연수 $a$, $n$에 대하여 $$ a^{\phi(n)} \equiv a^{2\phi(n)} \pmod{n} $$ 이다.
$a^{\phi(n)} \equiv a^{2\phi(n)} \pmod{n}$에서 주기가 $\phi(n)$으로 대충 잡을 수 있습니다. (단, 최소 주기가 아닐 수 있음)
아주 거대한 $b$에 대하여 $a^{b} \pmod{n}$의 값을 구할 때, $b$가 $\phi(n)$을 넘어가는 순간 주기가 생기는 것이다. ($\phi(n)$ 이하에선 무슨 일이 일어날지 모르니 다음 지수 탑을 $\phi(n)$을 나눈 나머지에서 꼭 $\phi(n)$을 더해주어야 함)
적당히 다음 지수탑을 보고 그냥 값을 도출할 수 있는 "상식적인 수준"이면 직접 값을 구해서 쓰고, 아니라면 안심하고 $[x_{1}, x_{2}, ..., x_{n}] \equiv {x_1}^{\left([x_2, ..., x_n] \pmod{\phi(n)}\right) + \phi(n)} \pmod{n}$을 이용해준다.
길이가 $5$만 넘어가도 "비상식적인 수준"이다. $2^{2^{2^{2^{2}}}} = 2^{2^{2^{4}}} = 2^{2^{16}} = 2^{65536}$
백준에도 power tower를 사용하는 문제들이 몇몇 존재함

참고자료 1
참고자료 2