백준 12446번: バクテリアの増殖 (Large)

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

12446번: バクテリアの増殖 (Large)

---

이전 포스팅에서 다뤘던 문제의 Large 버전입니다. ( 12445번: バクテリアの増殖 (Small) )

 

따로 더 필요한 논리는 없습니다.

 

수열 $\left \{ X_{n} \right \}$ 을 다음과 같이 정의합니다.

 

$X_{0}=A$

$X_{k}=\left ( X_{k-1} \right )^{X_{k-1}}$

 

구해야하는 건 마찬가지로 $X_{B}\;\; mod\;\; C$ 입니다.

 

그런데 $B$ 값이 Small 버전에 비하여 상당히 크기 때문에, 차근차근 어떤 값이 필요한지 살펴봅시다.

 

Euler's theorem을 이용하여 우선 다음 식을 얻습니다. (이 논의에서 $B$ 는 충분히 큰 값으로 생각합시다.)

 

$X_{B}\;\; mod\;\; C=\left ( X_{B-1}\;\; mod\;\; C \right )^{ \left ( X_{B-1}\;\; mod\;\; \phi \left ( C \right ) \right ) }\;\; mod\;\; C$

 

이제 수열의 정의에 따라 계속 따라가면 됩니다. 그래도 하나하나 다 쓰기엔 부담이 커서, 우선 한 단계만 풀어 써 보면 $\cdots$

 

$X_{B-1}\;\; mod\;\; C=\left ( X_{B-2}\;\; mod\;\; C \right )^{ \left ( X_{B-2}\;\; mod\;\; \phi \left ( C \right ) \right ) }\;\; mod\;\; C$

$X_{B-1}\;\; mod\;\; \phi \left ( C \right )=\left ( X_{B-2}\;\; mod\;\; \phi \left ( C \right ) \right )^{ \left ( X_{B-2}\;\; mod\;\; \phi \left ( \phi ( \left ( C \right ) \right ) \right ) }\;\; mod\;\; \phi \left ( C \right )$

 

즉, 다음 사실을 관찰할 수 있었습니다.

 

$\left ( 1 \right )$ $X_{B}\;\; mod\;\; C$ 를 얻기 위해 다음이 필요하다.

 

$X_{B-1}\;\; mod\;\; C$

$X_{B-1}\;\; mod\;\; \phi \left ( C \right )$

 

$\left ( 2 \right )$ $X_{B-1}\;\; mod\;\; C$ 와 $X_{B-1}\;\; mod\;\; \phi \left ( C \right )$ 를 얻기 위해 다음이 필요하다.

 

$X_{B-2}\;\; mod\;\; C$

$X_{B-2}\;\; mod\;\; \phi \left ( C \right )$

$X_{B-2}\;\; mod\;\; \phi \left ( \phi \left ( C \right ) \right )$

 

이 정도면 어느정도 감이 오실 것 같습니다.

 

이 문제의 시간제한이 30초이고, $B$ 의 값도 충분히 작기 때문에

 

메모이제이션 같은 것 없이 AC가 가능할 지도 모르겠네요.

 

하지만, 저의 경우는 미리 배열에 몇 가지 값들을 기록하여 시간을 줄였습니다.

 

Small버전과 마찬가지로 지수가 0이 되는 경우의 예외처리도 중요했습니다.

 

최종적인 코드는 다음과 같습니다.

#include <stdio.h>
#include <string.h>

int memo[1001];
int phi[1001];

int PHI (int X);

int power_modular (int X, int Y, int M);
int bacteria_modular (int A, int B, int C);

int main() {
	int T;
	scanf("%d", &T);
	int A, B, C;
	for (int i = 1; i <= T; i++) {
		memset(memo, 0, sizeof(memo));
		memset(phi, 0, sizeof(phi));
		scanf("%d %d %d", &A, &B, &C);
		printf("Case #%d: %d\n", i, bacteria_modular (A, B, C));
	}
	return 0;
}

int PHI (int X) {
	int answer = X;
	for (int i = 2; i * i <= X; i++) {
		if (X % i == 0) {
			while (X % i == 0) {
				X /= i;
			}
			answer -= answer / i;
		}
	}
	if (X > 1) {
		answer -= answer / X;
	}
	return answer;
}

int power_modular (int X, int Y, int M) {
	int answer = 1;
	while(Y) {
		if (Y & 1) {
			answer = answer * X % M;
		}
		X = X * X % M;
		Y >>= 1;
	}
	return answer;
}

int bacteria_modular (int A, int B, int C) {
	if (B == 1) {
		return power_modular(A, A, C);
	}
	int temp = C;
	while(temp > 1) {
		phi[temp] = PHI(temp);
		temp = PHI(temp);
	}
	temp = C;
	while(temp > 1) {
		memo[temp] = power_modular(A, A, temp);
		temp = phi[temp];
	}
	int idx = 1, K;
	while(idx < B) {
		temp = C;
		while(temp > 1) {
			K = phi[temp];
			memo[temp] = power_modular(memo[temp], memo[K] ? memo[K] : memo[K] + K, temp);
			temp = K;
		}
		idx++;
	}
	return memo[C];
}

(C11, 1124KB, 44ms, 제출번호 28475454)

---

제가 블로그에 쓰는 첫 다이아몬드 티어의 문제입니다!

 

그런데 너무 오래되서 코드를 봐도 기억이 잘 안 나는군요...

 

이런건 풀고 나서 바로바로 올려야 기억도 생생한데, 그럴 의욕이 안 들었어서...