덧셈, 뺄셈, 곱셈에 대해서는 다음 식이 항상 성립한다. (이부분에서는 mod M을 % M이라고 표현)
덧셈 : (a+b) % M = ((a % M) + (b % M)) % M
뺄셈 : (a-b) % M = ((a%M) - (b%M)) % M
곱셈 : (a*b) % M = ((a%M) * (b%M)) % M
나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다.
모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b와 M이 서로소(coprime)일 때만 존재한다.
곱셈 역원은 다음과 같은 방법으로 구할 수 있다.
- 페르마의 소정리 (Fermat’s Little Theorem)
- 확장 유클리드 호제법 (Extended Euclidean Algorithm)
출처
알고리즘 문제를 풀 때 종종 MOD 몇으로 나눈 값으로 답을 출력하라고 하는 경우가 있다.
사실 모듈로 연산이 아주 중요한 몇몇 문제를 제외하고는, 그냥 수가 커지는 것에 대한 방어책 정도라고 생각했다.
틀린 말은 아니지만, 모듈로 연산을 그냥 아주 떡칠을 할 수는 없는 노릇이다.
나눗셈에선 모듈로 연산이 적용이 안 될 수도 있기 때문이다.
https://www.acmicpc.net/problem/11505
최근 이 문제를 풀다가 모듈로 연산에서 나눗셈을 하는 것에 대해서 오류를 범했다.
모듈로 연산이 된 수를 나누는 것이 해의 안정성을 보장하지 못하는 것을 몰랐다.
결론적으로, 더하기 빼기 곱하기 연산에서는 모듈로로 떡칠을 하든 상관이 없지만,
나누기 연산 만큼은 조심하고 한번 더 생각하도록 하자.
코딩연습