BOJ 1629 곱셈

문제

접근 방법

b가 2,147,483,647까지 될 수 있기 때문에 O(N)으로 해결하려고 하면 안 된다. 따라서 O(logn)으로 풀 수 있는 방법을 생각해야 했다.

$a^{\frac{b}{2}} + a^{\frac{b}{2}} = a^b$

지수 성질을 사용하여 b를 2로 계속 나누어서 값을 구할 생각을 했다. 이렇게 하면 b번 곱해야 하는것을 logb로 바꿀 수 있다. 이때 b가 짝수면 상관없지마 홀수일 때는 b//2 + b//2 + 1 = b 이기 때문에 홀수인 경우를 따로 if문으로 처리했다.

정답 코드

import sys
input = sys.stdin.readline

a,b,c = map(int, input().split())

def multiply(b):
    if b==1:
        return a%c
    
    k = multiply(b//2)%c
    if b%2==0:
        return k*k%c
    else:
        return k*k*a%c
    
print(multiply(b)%c)