안 쓰던 블로그

알고리즘에서 나머지 연산은 연산의 값이 너무 커져서 자료형으로 담기 어려울 때, 각 연산마다 나머지 연산을 하여 자료형 안에 담기 위하여 사용한다 덧셈, 곱셈, 뺄셈은 성립하지만 나눗셈의 경우 성립하지 않는다. (나눗셈의 경우는 modular inverse를 구해야 한다) 그리고 주의할 점은 뺄셈의 경우 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 한 번 더하는 과정이 필요하다 $(A-B) mod M = ((A mod M) - (B mod M) + M) mod M$ 그 이유는 무엇일까? M을 더해도 전체 식에 영향은 없는 것인가? 나머지 연산에서 음수가 나오는 예시를 먼저 본다 $(6-5) mod 3 = 1 mod 3 = 1$ 이다 만약 $(6 mod 3-5 mod 3) mod..