백준 온라인 저지 - 13970. Power towers
오일러 파이 함수(Euler's totient function)은 정수론적 함수이다. $$\phi(n) = \left| \{ 1\leq m \leq n : \gcd(m, n) = 1 \} \right|$$ 로 정의된다. 페르마 소 정리부터 오일러 정리 등 KMO에서도 많이 다룬다. 코딩에서는 어디에 쓰일까? 단적인 예로는 확장 유클리드 호제법 없이 modular inverse를 구할 때 사용된다. $a^{\phi(p) - 1} \mod p$가 바로 $p$에 대한 $a$의 modular inverse이다. 좀 더 어려운 예시로는.. https://www.acmicpc.net/problem/13970 13970번: Power towers In this example, as M = 10, we are inte..
