[코딩테스트] 모듈러(%) 분배 법칙

모듈러 연산을 활용해 분배 법칙을 하면 우리가 흔히 분배 법칙으로 기대하는 결과와는 차이가 있다. 

• (A + B) % C = (A % C + B % C) % C
• (A - B) % C = (A % C - B % C + C) % C 
• (A * B) % C = ((A % C) * (B % C)) % C
• (A / B) % C = (A * B^(-1)) % C = ((A % C) * (B^(-1) % C)) % C

뺄셈의 경우 추가적으로 +C를 해주었는데 이러면 나머지 결과가 0 이상임을 보장할 수 있다. 코딩할 때 사실 결과로서 위 법칙만을 기억해도 괜찮을 것 같아서 증명 과정이 필요할까 싶지만... 과정을 알면 나중에 더 쉽게 기억할 수 있을 것 같아 첨부한다. 증명은 더하기만 확인해 보기로 한다. 어려워 보일 수 있는데 단지 치환해서 좌변=우변인지 확인하는 과정이고 여기서 우리가 일반적으로 모듈러 연산을 어떻게 사용하는지를 떠올려 보면 된다. 

(A + B) % C = (A % C + B % C) % C 증명

적용 예시

나누기는 B에 대한 역수를 취한 뒤 곱셈 법칙으로 바꾸어 계산한다.

• (A / B) % C = (A * B^(-1)) % C = ((A % C) * (B^(-1) % C)) % C

https://ohgym.tistory.com/13

모듈러 나눗셈

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction

Khan Academy