1629번: 곱셈

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

 

그냥 분할 정복을 이용한 거듭 제곱을 구현하고 나누면 끝인 거 아닌가? 라고 생각했는데,

수가 커질 때 나머지를 구하는 연산도 느려지는지 시간초과가 났다.

 

그래서 어떻게 해야하지 하면서 찾아보던 중

https://deepdata.tistory.com/369

분할정복을 이용한 거듭제곱 빠르게하기

위 블로그에서 중요한 정리를 하나 보여주었다.

이걸 보고 진짜인지 계산을 직접 해보았다.

 

예시로 $22^{3}$을 12로 나누었을 때 나머지를 구하는 것을 생각해보았다.

---

$n = 2$일 때,

$ a \times a = 22 \times 22$, $a = 484$

$ a \mod 12 = 4$

이 때 $ a' = a \mod 12$, 즉 $a' = 4$라고 해보자.

---

$n=3$일 때,

$ a \times a = 484 \times22 $, $a = 10648$

$ a \mod 12 = 4$

 

이 때, $a'^2 \mod 12 = 16 \mod 12 = 4$

---

$(22^2)^2 \to (22^2 \mod 12)^2 \to (22^2 \mod 12)^2 \mod 12$

$(a^2)^2 \to (a^2 \mod c)^2 \to (a^2 \mod c)^2 \mod c$

 

---

# https://www.acmicpc.net/problem/1629
# 분할정복

import sys

A, B, C = map(int, sys.stdin.readline().split())

def power(a, n, c) :
    result = 1
    while n :
        if n % 2 == 1 : # 홀수
            result *= a
        a *= a
        a = a % c
        n = n // 2
    return result

result = power(A, B, C)
print(result % C)