모듈러 연산의 특징

[(a mod n) + (b mod n)] mod n = (a+b) mod n

[(a mod n) - (b mod n)] mod n = (a-b) mod n

[(a mod n) * (b mod n)] mod n = (a*b) mod n

 

ex) (11 + 15) mod 8 = ((11 mod 8) + (15 mode 8)) mod 8 = (3+7) mod 8 = 2

       26 mod 8 = 2

 

이런 예시로는 효과가 별로 없어보이지만, 숫자가 커지면 효과를 느낄 수 있다.

 

11^7 mod 13. 11을 7번 곱할 수도 있지만 풀어서 쓰면 더 간단해진다.

((11 mod 13) * (11^2 mod 13) *(11^4 mod 13)) mod 13

 --> 11^2 mode 13 = 121 mode 13 = 4

 --> 11^4 = 11^2 * 11^2 = 4*4 = 16 mod 13 = 3

 = (11 * 4 * 3) mode 13 = 132 mod 13 = 2

 

단순히 저 계산을 못해서 저런 방법을 사용하는 것은 아니다.

 

알고리즘 문제에서 연산을 반복하다 보면 변수의 범위를 벗어나는 큰 수가 되는 경우가 있다.

이런 경우에는 정답을 mod x를 하여 출력 하도록 한다.

위 특징을 잘 활용하여, 값이 변수의 크기보다 커지기 전에 mod 연산을 활용하여 변수의 범위 내에서 연산할 수 있다.