[백준] 1629 - 곱셈(분할 정복, 수학)

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

1629번: 곱셈

a, b, c = map(int, input().split())
 
answer = 1
mul = a % c
while b > 0:
    if b % 2 == 1:
        answer *= mul
        answer %= c
    mul = ((mul % c) ** 2) % c
    b //= 2
print(answer)

직관적으로 b번만큼 루프 돌리면 터진다.

a^4 = (a^2)^2

이걸 이해하면 조금 수월하다.