[Python] 1629 - 곱셈 (실버1)

1. 문제 설명

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

1629번: 곱셈

 

---

2. 아이디어

반복문으로 풀면 무조건 타임에러가 난다.

A = 2,147,483,647 / B = 2,147,483,647 / C = 1 인 테스트 케이스가 들어오면

약 21억번의 연산이 들어가기 때문에 O(n)으로는 풀 수 없다.

그래서 분할 정복(O(logn))으로 풀어야 타임 에러에서 벗어날 수 있다.

 

예를 들어, \(2^{10}\)은 \(2^{5}\) x \(2^{5}\)로 나눌 수 있다.

홀수인 경우에는 \(2^{11} = 2^{5}\) x \(2^{5}\) x \(2\)가 된다.

이것만 안다면 매우 쉽게 해결할 수 있는 문제.

 

---

3. 코드

# 2,147,483,647 2,147,483,647 1 을 감당할 수 있는가?

def high_speed_pow(a, b, c):
    if b == 0:
        return 1
    value = high_speed_pow(a, b // 2, c)
    if b % 2 == 0:
        return (value ** 2) % c
    else:
        return ((value ** 2) * a) % c

def solution():
    a, b, c = map(int, input().split())
    ans = high_speed_pow(a, b, c)
    print(ans)

solution()