모듈러(Modular) 연산의 분배법칙 정리

허찬·2022년 3월 3일
0

Algorithm Study

목록 보기
3/4
post-thumbnail

알고리즘 PS를 하다 보면, 결과 값이 매우 큰 경우 결과 값을 특정 숫자로 나눈 나머지를 구하라는 문제가 종종 보인다. 이럴 때 모든 연산을 진행한 후 맨 마지막에 모듈러 연산을 하려고 하면 이미 자료형의 한계 범위를 넘어가서 '오버플로우'가 발생해 버리는 경우가 대다수다. 필자도 이러한 경우를 많이 겪어 봤지만, 겪을 때마다 금붕어처럼 까먹고 또 오버플로우를 발생시켜 왔다. 더 이상 이러한 상황을 만들지 않기 위해 이번 글을 쓴다.


위 문제의 해결책은 "모듈러 연산의 분배법칙"이다. 모듈러 연산의 분배법칙은 3가지가 존재한다.

  1.    (a+b) mod p=(a mod p+b mod p) mod p(a + b)~mod~p = (a~mod~p + b~mod~p)~mod~p
  2.    (a×b) mod p=(a mod p×b mod p) mod p(a \times b)~mod~p = (a~mod~p \times b~mod~p)~mod~p
  3.    (ab) mod p=(a mod pb mod p) mod p(a - b)~mod~p = (a~mod~p - b~mod~p)~mod~p

위 3가지 분배 법칙을 활용해서 계산 중간중간에 모듈러 연산을 섞어 줘야 값의 오버플로우를 방지할 수 있다.


앞으로는 절대 값의 오버플로우가 발생하지 않도록 신중을 기울이고, 철저히 검증하자.

profile
나 허찬

0개의 댓글