백준 온라인 저지 - 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

이런 문제에서 쓰인다.

$$ x_1 ^ {\left( x_2 ^ {\left( x_3 ^ {\left( x_4 ^ \cdots \right)} \right)} \right)} \mod m$$

을 구하는 문제이다.

 

오일러 정리에 따르면 $\gcd(a, m) = 1$인 자연수에 대해

$$a^{ \phi(m) } \equiv 1 \mod m$$

임은 안다. 하지만 두 자연수가 서로소가 아니면 문제는 곤란해진다.

 

 

다음 보조정리가 문제를 푸는데 도움된다. 2여년 전 쯤 과방에서 스윽하고 나타나 알려줬던 cubelover에게 감사의 인사를 보냅니다!

 

보조정리 1. 임의의 자연수 $a$, $m$에 대하여, $a^{\phi(m)} \equiv a^{2\phi(m)} \mod m$이다.

 

보조정리 2. 임의의 소수 $p$와 자연수 $e$에 대하여 $\phi(p^e) \geq e$를 만족한다.

 

(보조정리 2 증명) $\phi(p^e) = (p-1)p^{e-1} \geq (2-1)2^{e-1}$ 이므로 $2^{e-1} \geq e$ 를 보이면 충분하다. $e$에 대한 수학적 귀납법으로 증명된다.

 

(보조정리 1 증명) $m$과 $a$를 각각 소인수 분해하여 아래와 같이 표현하자.

$$ m = \prod_{i=1}^k p_i ^{e_i}, \: a = \prod_{j=1}^t q_j ^ {f_j} $$

또한, $m$과 $a$의 공통 소인수를 $\{p_1, p_2, \dots, p_u\} = \{q_1, q_2, \dots, q_u\} = \{p_1, p_1, \dots, p_k\} \cap \{q_1, q_2, \dots, q_t\}$ 라고 두자.

 

여기서 각 $1\leq j \leq t$에 대해, $q_j ^ {\phi(m)} \equiv q_j ^ {2\phi(m)} \mod m$ 만 보여도 충분하다.

 

$i)$ $1 \leq j \leq u$ 인 경우.

오일러 정리에 의해 임의의 $1 \leq i \leq k$, $i \neq j$ 에 대해, $q_j ^ {\phi(p_i ^ {e_i})} \equiv q_j ^ {\phi(m)} \equiv q_j ^ {2\phi(m)} \equiv 1 \mod p_i^{e_i}$ 인 것은 자명하다. 보조정리 2에 의해 $\phi(m) \geq \phi(p_j ^ {e_j}) \geq e_j$ 이므로, $q_j ^ {\phi(m)} \equiv q_j ^ {2\phi(m)} \equiv 0 \mod p_j^{e_j}$ 이다. $q_j ^{\phi(m)}$ 과 $q_j^{2\phi(m)}$ 을 $(p_1^{e_1}, p_2^{e_2}, \dots, p_k^{e_k})$ 로 나눈 나머지가 서로 같다. 중국인의 나머지 정리에 의해 둘은 $m$으로 나눈 나머지도 서로 같다.

 

$ii)$ $j > u$ 인 경우.

$\gcd(q_j, m) = 1$ 이므로 오일러 정리에 의해 $q_j^{\phi(m)} \equiv q_j^{2\phi(m)} \equiv 1 \mod m$ 이다.

 

 

보조정리를 구체적으로 어떻게 사용할까. $a^p \mod m$ 을 구할 때 다음과 같은 방법으로 구하면 된다.

• $0 \leq p < \phi(m)$ 인 경우. $a^p \mod m$ 을 비트연산자를 이용하여 $O(\log p)$에 구한다.
• $\phi(m) \leq p$ 인 경우. $a^p \equiv a^{(p \mod \phi(m)) + \phi(m)} \mod m$ 을 이용한다!

이 성질을 이용하여 재귀함수를 하나 만들자. $f(i, \phi(m))$ 은 다음 성질을 만족하는 함수이다.

$$ x_{i-1} ^ { \left( x_i ^ { \left( x_{i+1} ^ \cdots \right) } \right) } \equiv x_{i-1} ^ {f(i, \phi(m))} \mod m $$

보조정리들에 의해 $f$를 계산하는 과정은 다음과 같다.

$$ f(i, m) = \left\{ \begin{array}{ll} 1 & \text{if $m$ = 1} \\ x_i & \text{if $i = n$} \\ x_i ^ {f(i+1, \phi(m))} & \text{if $x_i ^ {f(i+1, \phi(m))} < m$} \\ x_i ^ {f(i+1, \phi(m))} + m & \text{if $x_i ^ {f(i+1, \phi(m))} \geq m$} \end{array} \right. $$

 

그러므로 $n>1$ 인 경우에 대해서 $f(2, \phi(m))$ 을 구한 후 modular power를 계산해주면 최종 결과를 얻을 수 있다.

 

 

사실 $\phi(\phi(\phi(\cdots \phi(m))) \cdots)$ 이 1로 수렴하는데 걸리는 합성함수의 개수는 $O(\log_2 m)$ 이다. $\phi(x)$ 값이 $x$가 홀수라면 짝수 값을 가지고, $x$가 짝수라면 $x/2$ 이하로 줄어들기 때문이다. 실질적인 재귀함수의 깊이는 얼마 되지 않는다.

 

 

오일러 파이 함수는 naive하게 $O(\sqrt m)$에 계산할 수도 있지만 $m$의 제한이 비교적 작은 경우(한 $10^6$ 정도)는 에라토스체처럼 이쁘게 precompute 하는 방법이 있다.

 

$m = \prod_{i=1}^k p_i ^ {e_i}$ 로 두자.

$$ \begin{align} \sum_{d | m} \phi(d) &= \prod_{i=1}^k \left( \sum_{j=0}^{e_i} \phi(p_i ^ j) \right) \\ &= \prod_{i=1}^k \left( 1 + (p_i - 1) (1 + p_i + p_i^2 + \cdots + p_i^{e_i - 1}) \right) \\ &= \prod_{i=1}^k \left(1 + (p_i - 1) \cdot \frac{p_i ^ {e_i} - 1}{p_i - 1} \right) \\ &= m \end{align} $$

 

이 성질을 이용하면 아래와 같이 $O(m \log m)$ 만에 체를 만들 수 있다.

const int MAX_M = 1<<20;
int phi[MAX_N];
for (int i=0; i<MAX_M; i++) phi[i] = i;
for (int i=1; i<MAX_M; i++)
    for (int j=i+i; j<MAX_M; j+=i)
        phi[j] -= phi[i];

 

 

Note. (맞왜틀 팁) $a^x \equiv a^{(x \mod \phi(m)) + \phi(m)} \mod m$ 으로 푸시면 안 됩니다.. $x > \phi(m)$ 인 경우만 이 등식이 성립하고, $x \leq \phi(m)$ 이라면 성립하지 않습니다.

 

비슷하게 풀 수 있는 꿀문제(알려주신 evenharder, queued_q님 감사합니다!)

 

https://www.acmicpc.net/problem/16214

16214번: N과 M

https://www.acmicpc.net/problem/13358

13358번: Exponial