큰 수의 모듈러 연산

32bit 정수형의 범위를 넘는 큰 수에 모듈러(modulo) 연산을 하려면 어떻게 해야 할까요?

모듈러 연산의 특성을 활용하면 됩니다.

 

정수 \(a, b\)를 \(M\)으로 나눈 나머지가 각각 \(a', b'\)라고 하겠습니다. 이 때 \(a+b\)를 \(M\)으로 나눈 나머지는 얼마일까요?

\begin{align}
a &= xM+a' \\
b &= yM+b' \\
a+b &= (x+y)M+(a'+b') \\
(a+b) \% M &= (a'+b') \% M
\end{align}

이렇게 유도돼서 결국은 \( (a+b)\%M=((a\%M)+(b\%M))\%M \) 라는 공식이 나오게 됩니다. 이런 성질은 덧셈, 뺄셈, 곱셈에 모두 성립합니다. (나눗셈은 제외)

 

\begin{align}
(a+b)\%M &= ((a\%M)+(b\%M))\%M \\
(a-b)\%M &= ((a\%M)-(b\%M)+M)\%M \\
(a \times b)\%M &= ((a\%M) \times (b\%M))\%M
\end{align}

뺄셈의 경우, mod 연산을 한 결과가 음수가 나올 수 있기 때문에 \(M\)을 더해줘야 합니다.

위 모듈러 공식을 이해하고 있으면 알고리즘 문제 풀 때 요긴하게 쓰입니다