소수 법에서 계산하기

대회 문제의 답은 다른 곳에서 사용하는 어떤 정수 자료형의 범위도 훨씬 넘어설 만큼 커질 수 있습니다. 그래서 문제에서는 수를 작게 유지하기 위해 결과를 큰 소수로 모듈러 연산한 값을 요구합니다. 🔢

가장 자주 보게 될 소수는 1000000007이며, 흔히 1e9+7로 씁니다. 충돌을 피할 만큼 크면서도 64비트에 들어갈 만큼 작습니다.

모듈러 연산자는 나눗셈 후의 나머지를 반환합니다. 따라서 17 % 5는 2입니다. 17을 5로 나누면 나머지가 2이기 때문입니다.

먼저 더한 뒤 마지막에 모듈러 연산을 할 수도 있고, 계산하는 동안 계속 모듈러 연산을 할 수도 있습니다. 어느 쪽이든 나머지는 같으므로, 수를 작게 유지하려면 자주 줄이세요.

곱셈에도 같은 규칙이 적용됩니다. 곱을 소수로 모듈러 연산하세요. 파이썬은 큰 정수를 기본적으로 처리하지만, 모듈러 연산을 하면 모든 값이 작아져 더 빠르게 계산할 수 있습니다.

긴 반복문에서는 매 반복마다 % MOD를 적용하세요. 그러면 수가 지나치게 커지는 것을 막고 각 연산을 저렴하고 예측 가능하게 유지할 수 있습니다.

뺄셈은 많은 언어에서 음수 나머지를 만들 수 있습니다. 최종 모듈러 연산 전에 MOD를 다시 더해 결과가 안전한 0 이상 범위에 들어오게 하세요.

좋은 소식이 있습니다. 파이썬의 %는 양의 모듈러에 대해 이미 음수가 아닌 결과를 반환합니다. 따라서 -1 % 7은 -1이 아니라 6이므로 따로 보정할 필요가 없습니다.

핵심 개념은 다음과 같습니다. 덧셈과 곱셈에 대해 (a op b) % m은 (a%m op b%m) % m과 같습니다. 따라서 두 값을 결합하기 전에 입력을 줄일 수 있습니다.

덧셈, 뺄셈, 곱셈은 모듈러 아래에서 깔끔하게 작동하지만 일반적인 나눗셈은 그렇지 않습니다. 이 과정의 뒤쪽에서 모듈러 역원이 필요합니다.

해답의 시작 부분에서 MOD를 상수로 정의하세요. 코드 곳곳에 1000000007을 흩어 놓는 것보다 이름을 붙인 값 하나를 사용하는 편이 좋으며, 오타도 쉽게 찾을 수 있습니다.

뺄셈을 모듈러 연산하기 전에 MOD를 더하는 이유는 무엇인가요?

이제 1e9+7 같은 소수 모듈러를 사용해 큰 개수를 작게 유지할 수 있습니다. 매 단계에서 덧셈, 뺄셈, 곱셈의 결과를 줄이고 음수를 주의하며, 나눗셈은 역원을 사용할 때까지 미뤄 두세요. 🎯