[Algorithm] 나머지를 통해서 해를 구할 때 이용하는 공식
알고리즘 문제를 풀 때 연산의 결과가 너무 커서 어떠한 수로 나눈 나머지를 통해 해를 답을 구하는 경우가 있는데 이 때 어떻게 이용할 수 있는지 보자
환경 및 선수조건
- C++
공식
- 합:
(A + B) % M = ((A % M) + (B % M)) % M - 곱:
(A X B) % M = ((A % M) X (B % M)) % M - 차:
(A - B) % M = ((A % M) - (B % M) + M) % M - 뺄셈의 경우에는
%결과가 음수로 나올 수 있기 떄문에M을 더해준다
유도(덧셈만)
다음 아래 사진처럼 식 유도가 가능합니다
