[Algorithm] 모듈러 연산

알고리즘 문제를 푸는데 많이 나오는 모듈러 연산!

이걸 몰라서 틀리면 억울하니 알아만 두자.

 

• (𝑎+𝑏) % 𝑀 = ((𝑎 % 𝑀)+(𝑏 % 𝑀)) % 𝑀
• (𝑎−𝑏) % 𝑀 = ((𝑎 % 𝑀)−(𝑏 % 𝑀)+𝑀) % 𝑀
• (𝑎×𝑏) % 𝑀 = ((𝑎 % 𝑀)×(𝑏 % 𝑀)) % 𝑀

덧셈, 뺄셈, 곱셈에는 대체로 잘 적용하나 나눗셈은 그렇지 않다. 페르마 소정리를 이용해야 하는데 아래의 블로그에 잘 정리되어 있다. 

 

https://ohgym.tistory.com/13

모듈러 나눗셈

 

어쨋든 결론만 기억하자면, 

• (𝑎/𝑏) % 𝑀 = ((𝑎 % 𝑀)×(𝑏^(𝑀−2) % 𝑀)) % M 

M이 소수여야 하고, b는 M의 배수이면 안된다.