[백준 1629번] 곱셈 - python

문제 링크

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

1629번: 곱셈

풀이 

- dp로 해결하려 했지만 메모리 초과 

예 ) a = 2147483646, b = 2147483646 , c = 2147483647 처럼 숫자가 너무 큰 경우 해결 안됨 

# 메모리 초과 
a, b, c = map(int,input().split())

dp = [1] * (b+1) 
for i in range(1,b+1):
  dp[i] = (dp[i-1] * a) % c

print(dp[b])

- 다른 블로그를 참고하니 분할 정복 문제 

- b가 짝수인지 홀수 인지 판단하여 분할 정복

예 ) b = 10 이라고 할 때 

a ^ 10  -> (a ^ 5) ^2 꼴로 변경 

a ^ 11 -> (a ^ 5)^ 2 * a 꼴로 변경  

나머지 분해 법칙으로 구하기 위해서 

: (AxB)%C = (A%C) *(B%C) % C

def power(a,b):
  # b가 1이면 a를 c로 나눈 나머지 반환 
  if b == 1 :
    return a % c 
  else :
    # a ^ ( b//2 ) 
    temp = power(a, b//2)    
    if b % 2 == 0:
      return temp * temp % c 
    else:
      return temp * temp * a % c 
    
a, b, c = map(int,input().split())

print(power(a,b))