[Algorithm] 백준 알고리즘 기초 1/2 - 나머지 연산

나머지 연산

컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 $M$으로 나눈 나머지를 출력하라는 문제가 등장한다.

Overflow 문제와 덧셈

$(A+B)\mod{B}$


하지만, 위 식에서 만약 $A+B$의 연산 결과가 자료형의 범위를 넘어서게 되면 overflow가 발생한다.
이 때, $A$와 $B$ 각각에 나머지 연산을 적용하여 overflow를 막을 수 있다.


$(A+B)\mod{M}=((A\mod{M})+(B\mod{M}))\mod{M}$

곱셈

곱셈은 덧셈의 연속이기 때문에 곱셈에서는 다음의 식이 성립한다.


$(A\times{B})\mod{M}=((A\mod{M})\times{(B\mod{M})})\mod{M}$

나눗셈

나눗셈에서는 성립하지 않고 모듈러 역수(Modular Inverse)를 구하여 해결한다.


$(A\div{B})\mod{M}\neq((A\mod{M})\div{(B\mod{M}))}\mod{M}$

뺄셈

뺄셈의 경우에는 먼저 $\mod{}$ 연산을 한 결과가 음수가 나올 수 있기 때문에 $M$을 더해야 한다.


$(A-B)\mod{M}=((A\mod{M})-(B\mod{M})+B)\mod{M}$


만약 M을 더하지 않아 $\mod{}$ 연산을 한 결과가 음수가 나오면 언어별로 다른 결과가 나온다.
예를 들어, $((6\mod{3})-(5\mod{3}))\mod{3}$의 결과가 C11, C++14, Java는 -2이고 Python3는 1이다.