[BOJ] 곱셈 (1629)

---

코드

import sys
input = sys.stdin.readline

def solution(a,b):
    if b == 1:
        return a % C
    
    temp = solution(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(solution(A,B))

결과

풀이 방법

• 나머지 분배법칙과 분할정복을 활용하는 문제이다
• 나머지 분배법칙: (a x b) % c = (a % c) x (b % c) % c
• b가 짝수일 때 (A^b) % c = (A^(b//2) % c) * (A^(b//2) % c) % c
• b가 홀수일 때 (A^b) % c = (A^(b//2) % c) (A^(b//2) % c) A % c
• 재귀함수 호출을 줄이기 위해 미리 (A^(b//2) % c) 값을 구하여 저장해놓고 사용해야 한다.

---