나머지(Modulo)(%) 연산에서 분배법칙 정리

알고리즘 문제를 풀다 보면 자주 등장하는 것이 나머지 연산입니다. 특히 문제에서 결과값이 매우 커질 수 있는 경우, % MOD를 취해 정답을 구하는 경우가 많습니다.

하지만 모듈러 연산의 분배법칙에는 몇 가지 주의할 점이 있습니다.

• 덧셈, 곱셈에서는 분배법칙이 잘 적용되지만,
• 뺄셈에서는 음수가 나올 수 있어 보정이 필요합니다.
• 나눗셈은 분배법칙이 성립하지 않기 때문에 페르마의 소정리를 써야 합니다. (MOD가 소수이고, a가 MOD로 나누어떨어지지 않는 정수일 때만 성립)

// 덧셈
(a + b) % MOD == ((a % MOD) + (b % MOD)) % MOD
// 곱셈
(a * b) % MOD == ((a % MOD) * (b % MOD)) % MOD
// 뺄셈
(a - b) % MOD == ((a % MOD) - (b % MOD) + MOD) % MOD
// 나눗셈
(a / b) % MOD != ((a % MOD) / (b % MOD)) % MOD
(a / b) % MOD == (a * b^(MOD-2)) % MOD == ((a % MOD) * (b^(MOD-2) % MOD)) % MOD