[BOJ] 1629. 곱셈(python)

📌문제

💪아이디어

내장함수 pow()로 거듭제곱을 구현할 경우 시간복잡도가 O(N)이다. N이 1e6이기 때문에 O(logN)의 알고리즘을 구현해야한다.

\[f(a,b) = \begin{cases} a^{b//2}\ * \ a^{b//2}, & \text{if b is even} \\ a^{b//2}\ * \ a^{b//2} \ * \ a, & \text{if b is odd} \end{cases}\]

이 재귀함수는 b//2를 하면서 b==0이 되면 종료된다.

🥂코드

import sys; input = sys.stdin.readline
a, b, c = map(int,input().split())

answer = 1
while b > 0:
    if b % 2 != 0:
        answer = (answer * a) % c
    b //= 2
    a = (a * a) % c
print(answer)