alphago92   8달 전

알고리즘 입문자입니다

dp문제를 풀다보면

값이 커져서 그런지 mod를 해서 출력하라는 문제들이 많더라구요

배열에 각 값을 저장한다음에 

출력할때만 mod 를 하면 오버플로우가 나더군요


그래서 그런데 mod연산에 대한 

계산법칙 같은게 있나요?

예컨대 (a+b)mod = amod + bmod 라던가...

네이버, 구글에 찾아봐도 잘 나오지않아 질문드립니다

dotorya   8달 전

사칙연산은 전부 성립합니다.

a + b mod M = (a mod M + b mod M) mod M

(a-b)%M = (a%M-b%M)%M

(단, 음수의 mod는 양수로 맞춰주는 게 편합니다. 예를 들어 -1%3 = 2 등.. C언어의 % 연산자는 저 값을 -1로 계산하니 주의하세요.)

(a×b)%M = (a%M×b%M)%M

(a/b)%M = (a%M×(1/b)%M)%M

(1/b mod M은 b×c = 1 (mod M)인 c를 말합니다. M이 소수인 경우 0이 아닌 모든 b에 대해서 존재하며, 많은 문제에서 사용하는 10^9+7은 소수입니다. 더 자세히 알고 싶다면 modular inverse로 검색해 보세요.)

alphago92   8달 전

dotorya형 사랑해요..

댓글을 작성하려면 로그인해야 합니다.