[알고리즘] 나머지연산(Modular Arithmetic : mod)

나머지연산 (mod)

알고리즘 문제 중에서 답을 낼 때 구한 값의 나머지를 구해야하는 경우가 종종 있다. 구한 값이 int형이나 long형의 표현가능 범위를 벗어나게 되는 경우 mod연산을 통해 크기를 줄일 수 있다.

사칙연산에 대하여 모듈러 연산은 다음과 같이 성립한다.

$(A+B)mod C = (AmodC + BmodC) modC$
= (A+B)% C = (A%C + B%C) %C

$(A-B)mod C = (AmodC - BmodC) modC$
= (A-B)% C = (A%C - B%C) %C
❕ 음수가 나왔을 때는 C를 더해주면 된다.

$(A*B)mod C = (AmodC * BmodC) modC$
= (A*B)% C = (A%C * B%C) %C

⚠ 나눗셈은 위 법칙이 성립되지 않는다.
모듈러 나눗셈 방법 참고