1629 곱셈

아이디어

조건에서 어렴풋이 제곱의 형태로 재귀함수가 구현되어야 할 것 같다는 느낌은 받았지만,
기저조건을 어떻게 코드로 작성해야 할지 감이 오지 않았다.

모듈러 연산을 좀 찾아보고 나서 감이 왔다.
(출처 - https://gliver.tistory.com/5)

구현

import sys

input = sys.stdin.readline

a_, b_, c_ = list(map(int, input().split()))


def super_remainder(a, b, c):
    if b == 1:
        return a % c
    else:
        if b % 2 == 1:
            return ((super_remainder(a, b // 2, c) ** 2) * super_remainder(a, 1, c)) % c
        else:
            return (super_remainder(a, b // 2, c) ** 2) % c


print(super_remainder(a_, b_, c_))

(a^2) % c = (a%c)^2임을 이용,
b=1일 때가 기저조건이고, 그 이상일 때는 b가 홀수일 때와 짝수일 때를 나눠서 처리했다.