백준 1629 곱셈(파이썬)
접근방식
- 문제는 쉬워보이는데 어떻게 분할하면 좋을지 감이 안잡혔다.
- 블로그를 참고하니 b의 값이 짝수인지 홀수인지 파악하여 짝수라면 (A^(B//2))^2의 형태로 홀수라면 (A^(B//2))^2*A의 형태로 바꾸어 값을 구한다.
파이썬 코드
import sys
a, b, c = map(int,sys.stdin.readline().split())
def cal(a, b, c):
if b == 1:
return a % c
else:
temp = cal(a, b // 2, c)
if b % 2 == 0:
return temp * temp % c
else:
return temp * temp * a % c
print(cal(a, b, c))
