백준 12445번: バクテリアの増殖 (Small)

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

12445번: バクテリアの増殖 (Small)

---

번역기를 돌려보면 대충 문제가 말하는 것을 파악할 수 있습니다.

 

초기의 박테리아의 수는 문제에서 주어지는 인풋인 $A$ 이니까, 수열 $\left \{ X_{N} \right \}$ 을 이렇게 정의합시다.

 

$X_{0}=A$

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

 

우리는 $B$ 를 인풋받아 $X_{B}$ mod $C$ 를 구해야 합니다.

 

이 문제는 Small 버전이라서, $1\leq B\leq 2$ 입니다.

 

따라서, 각각의 케이스에 대해 구현할 수 있습니다.

 

$B=1$ 일 때는, 단순히 $A^{A}$ mod $C$ 를 구하면 됩니다.

 

$B=2$ 일 때는, euler's theorem을 활용합니다.

 

즉, 다음과 같습니다.

 

$\left ( A^{A} \right )^{ \left ( A^{A} \right ) }\;\; mod\;\; C = \left ( A^{A}\;\; mod\;\; C \right )^{\left ( A^{A}\;\; mod\;\; \phi \left ( C \right )\right )}\;\; mod\;\; C$

 

단, 지수 부분이 0이 되지 않도록 예외처리를 조금 해주어야 합니다.

 

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

#include <stdio.h>

int phi (int X);
int power_modular (int X, int Y, int mod);

int main() {
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		int A, B, C;
		scanf("%d %d %d", &A, &B, &C);
		
		int Answer;
		if (B == 1) {
			Answer = power_modular (A, A, C);
		}
		else {
			int Base = power_modular (A, A, C);
			
			if (Base == 0) {
				Answer = 0;
			}
			else {
				int Power = power_modular (A, A, phi(C));
				if (Power == 0) {
					Power += phi(C);
				}
				Answer = power_modular (Base, Power, C);
			}
		}
		
		printf("Case #%d: %d\n", i, Answer);
	}
	return 0;
}

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

int power_modular (int X, int Y, int mod) {
	int answer = 1;
	while(Y) {
		if (Y % 2) {
			answer = (answer * X) % mod;
		}
		X = (X * X) % mod;
		Y /= 2;
	}
	return answer;
}

(C11, 1116KB, 0ms, 제출번호 27527547)

---