[baekjoon] 백준 1629번 : 곱셈 (by python 파이썬) 수학, DAC(분할정복)

정답 code

# 곱셈
import sys
input = sys.stdin.readline

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

def power(a,b):
    if b == 1:
        return a%c
    else:
        tmp = power(a,b//2)
        if b%2 == 0:
            return tmp * tmp % c #b가 짝수
        else:
            return tmp*tmp* a % c #b가 홀수

print(power(a,b))

 

solution

이 문제는 단순하게 모두 곱한후 나누면 시간초과가 난다.

따라서 분할정복을 통해 나눠서 계산해줘야되는데

10 ^ 11 = 10^5 * 10^5 * 10 이런식으로 분할하여 시간을 줄여주는 것이다.

 

만약 b가 짝수라면 a를 한번더 곱해주지 않고

10 ^ 10 = 10^5 * 10^5 로 가능하다

 

따라서,

짝수인 경우 tmp * tmp % c

홀수인경우 tmp * tmp * a % c

를 통해 해결 할 수있다.