[Baekjoon/python] 곱셈 #1629

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

1629번: 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

코드

• 분할정복 적용
• memoization을 사용하여 이미 구한 값들을 저장 (안하면 시간초과)

import sys

input = sys.stdin.readline

A, B, C = map(int, input().split())

memo = {1: A % C}

def dfs(n):
    if n in memo:
        return memo[n]
    
    result = (dfs(n // 2) * dfs(n - n // 2)) % C
    memo[n] = result
    return result

print(dfs(B))