[C++]모듈로 사칙연산

모듈로 연산이란 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 흔히 %로 사용한다.

모듈로 연산은 나눗셈을 제외한 사칙연산에서 분배 법칙이 적용되는데, 식으로 정리하면 다음과 같다.

(a+-b)%c = (a%c+-b%c)%c
(a*b)%c = (a%c*b%c)%c
(참고 : if a%c == b%c, (a^n)%c == (b^n)%c)

간단히 말하면, 모듈로 연산을 사칙연산 이전에 수행하든, 사칙연산을 끝낸 뒤 수행하든 나머지는 같다.