1629 곱셈 (Python)

문제 : https://www.acmicpc.net/problem/11049

 

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

R = A % C

def remainder(A, B, C):
    R = A % C
    if B == 1:
        return R
    elif B % 2 == 0: # 지수가 짝수면
        R = remainder(R*R, B//2, C)
        return R
    else:
        R = remainder(R*R,B//2,C) * R
        return R

print(remainder(A,B,C)%C)

 

A를 C로 나눈 나머지가 R이라 하면,
A^B % C == R^B % C 이다.

 

A = (몫*C) + R 이므로,
{(몫*C) + R} * {(몫*C) + R} * {(몫*C) + R}... 일때,
R^B를 제외한 나머지 항들은 C에 의해 깔끔히 나눠지기 때문이다.