백준 1629번 곱셈

문제 풀이

• 단순히 제곱을 해버리면 시간 초과
• 제곱을 반씩 쪼개면서 재귀로 점점 분해 해주는 트릭이 필요합니다.
• 값이 커지는 걸 방지하기 위해 계산마다 C로 나눠줍니다.

예시

A = 10, B = 11, C = 12

• 계산식: 10 ^ 11 % 12

1/2로 분해 => B % 2 = 1 ( B = 11 )
(10 ^ 5) % 12 X
(10 ^ 5) % 12 X
10 % 12

1/2로 분해 => B % 2 = 1 ( B = 5 )
(10 ^ 2) % 12 X (10 ^ 2) % 12 X 10 % 12 X
(10 ^ 2) % 12 X (10 ^ 2) % 12 X 10 % 12 X
10 % 12

1/2로 분해 => B % 2 = 0 ( B = 2 )
(10 % 12 X 10 % 12) X (10 % 12 X 10 % 12) X 10 % 12 X
(10 % 12 X 10 % 12) X (10 % 12 X 10 % 12) X 10 % 12 X
10 % 12

• 우리는 10의 11제곱을 모두 계산할 필요가 없습니다.
• 반씩 분해해서 제일 아래로 내려가 10 % 12를 계산한 뒤 그 값을 거슬러 올라오면서 제곱해주면 됩니다.
• 거슬러 올라오면서, 반씩 나눴던 B가 2로 딱 나누어 떨어지면 단순히 제곱하고,
  2로 나누어 떨어지지 않으면 제곱 X 10 % 12를 계산하면 됩니다.
• 값이 커지는 걸 방지하기 위해 계산마다 C로 나눈 나머지를 계산합니다.

코드 풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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


def multiply(A, B):
    if B == 1:
        return A % C
    else:
        result = multiply(A, B // 2)
        if B % 2 == 0:
            return (result * result) % C
        else:
            return (result * result) * (A % C) % C


print(multiply(A, B))