[Python] 12445번 バクテリアの増殖 (Small)

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

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

---

 

24/02/09

 

 

아주 아주 간단한 문제로, 파이썬으로 해결하기에 아주 적절한 문제다.

---

 

문제 접근 방식:

 

 

이 문제는 Small버전이 존재하고 Large버전이 존재한다.

 

Large버전의 경우, Power tower류의 문제로, 정수론을 배워야 풀 수 있는 문제다.

 

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

13970번: Power towers

 

하지만 Small버전은 그 제한이 매우 작기 때문에, 파이썬으로 아주 간단하게 구현할 수 있다.

 

문제를 해석하면 다음과 같다.

 

$x$마리의 박테리아는 $1$시간이 지날 때 마다 $x^x$마리의 박테리아로 증식한다.

 

$A$마리의 박테리아가 $B$시간 후 몇 마리가 될지 $C$로 나눈 나머지를 출력하면 된다.

 

Small문제의 경우 $B$가 $1$또는 $2$로 제한되어 있다.

 

또한 $A$의 제한이 $1000$까지로, 매우 작다.

 

파이썬은 $1000^{1000}$은 너끈히 계산할 수 있으므로, 그냥 이를 그대로 구현하면 된다.

 

pow함수는 밑, 지수, 나머지의 세 인자를 받아 $a^b$를 나머지로 나눈 값을 출력해 주는 아주 좋은 함수다.

 

또한, 파이썬의 pow함수는 분할 정복을 이용한 거듭제곱으로 구현되어있기 때문에 $\mathcal{O}(\mathrm{log}N)$이라는 빠른 시간 복잡도로 구할 수 있다.

 

이 함수를 사용하면 빠르게 해결할 수 있다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 12445번 バクテリアの増殖 (Small)
# 수학, 분할정복을 이용한 거듭제곱
import sys
input = sys.stdin.readline

def main():
    T = int(input())
    for i in range(1, T+1):
        a, b, c = map(int, input().rstrip().split())
        if b == 1:
            print(f'Case #{i}:', pow(a, a, c))
        else:
            print(f'Case #{i}:', pow(pow(a, a), pow(a, a), c))

main()