모듈러 연산

백준 곱셈문제를 풀며 모듈러 연산을 공부하였다.

모듈러 연산이란 나머지를 구하는 연산자로 위의 분배법칙이 성립한다.

 

곱셈에 대한 분배법칙의 증명은 다음과 같다.

모듈러 연산을 응용한 백준 곱셈 문제 풀이

import sys
input = sys.stdin.readline

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

def Rest(r,B):
    if B == 1:
        return r
    else:
        tmp = Rest(r,B//2)
        if not B%2:
            return tmp*tmp%C
        else:
            return tmp*tmp*r % C 


print(Rest(r,B))