백준 16214: N과 M

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

16214번: N과 M

---

일반적인 power tower 유형에서 모든 지수에 $N$을 넣어준 것이므로 난이도가 어떤 면에선 더 쉬워졌다고 볼 수 있습니다.

 

본문은 매우 훌륭한 자료인 https://rkm0959.tistory.com/181 을 인용했습니다.

---

위 글에 따르면 다음이 성립합니다. (Notation은 위 링크를 참조해주시기 바랍니다.)

$$ [N,N,N, \cdots ] = N^{ \left \{ [N,N,N, \cdots ] \; \textrm{mod} \; \phi (m) \right \} + \phi (m)} \;\; \textrm{mod} \;\; m $$

그 이유는, 주어진 범위의 모든 $M$에 대해 $[N,N,N, \cdots]$가 $\log_{2} M$ 보다 크기 때문입니다.

 

따라서 $\phi ( \phi ( \cdots (M)) \cdots ) = 1$인 순간부터 다시 역으로 내려오는 알고리즘을 짜면 문제가 해결됩니다.

---

예외처리는 $N=1$, $M=1$, $M=2$에 대해 해주면 충분합니다. 자명하게 각각의 답은 $1 \; \textrm{mod} \; M$, $0$, $N \; \textrm{mod} \; 2$ 입니다.

 

다음은 제 코드입니다.

#include <stdio.h>

long long PHI (long long N);
long long power_modular (long long X, long long Y, long long M);
long long infinite_power_tower_modular (long long N, long long M);

int main() {
	
	int T;
	scanf("%d", &T);
	while(T--) {
		long long N, M;
		scanf("%lld %lld", &N, &M);
		printf("%lld\n", infinite_power_tower_modular(N, M));
	}
	return 0;
}

long long PHI (long long N) {
	long long result = N;
	for (long long i = 2; i * i <= N; i++) {
		if (N % i == 0) {
			result -= result / i;
			while(N % i == 0) {
				N /= i;
			}
		}
	}
	if (N > 1) {
		result -= result / N;
	}
	return result;
}

long long power_modular (long long X, long long Y, long long M) {
	long long result = 1;
	while(Y) {
		if (Y % 2) {
			result = result * X % M;
		}
		X = X * X % M;
		Y /= 2;
	}
	return result;
}

long long infinite_power_tower_modular (long long N, long long M) {
	if (N == 1 || M <= 2) {
		return N % M; // below is for N > 1 and M > 2
	}
	
	int size = 1;
	long long phi[50] = {M};
	for (long long i = 1; i < 50; i++) {
		phi[i] = PHI(phi[i-1]);
		if (phi[i] == 1) {
			size = i;
			break;
		}
	}

    long long array[50] = {};
	array[size] = 1;
	for (int i = size - 1; i > 0; i--) {
		array[i] = power_modular(N, array[i+1], phi[i]) + phi[i];
	}
	array[0] = power_modular(N, array[1], M);
	
	return array[0];
}

(C11, 88ms, 1116KB, 제출번호 54348753)

---

만약 13970번을 먼저 풀었다면 해당 문제 정답 코드에 수열의 길이를 대략 5~60으로 부여하여 각 항을 $N$으로 넣어도 풀리지 않을까 했는데, 정말 그렇게 한 분이 있을지는 잘 모르겠습니다.

 

최고 속도를 내신 분들은 어떻게 풀었나 했는데, totient function의 정의가 $\prod \left ( 1-\frac{1}{p_{k}} \right ) $이기 때문에 sieve를 활용하는 것도 좋은 방법이었던 것 같습니다. 소수의 집합을 통해 sieve를 진행하면 복잡도가 linear해진다고 합니다. 거기에 Totient function이 multiplicative하다는 것까지 쓰는 것 같은데, 언제 한 번 공부해보고 싶어지는 코드입니다.