나머지 연산

• 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제가 등장함.
• (A+B) mod M = ((A mod M) + (B mod M)) mod M
  • (5 + 2) % 3 = 7 % 3 1
  • (5 % 3 + 2 % 3) % 3
  • (2 + 2) % 3 = 4 % 3 = 1
• (AXB) mod M = ((A mod M) X (B mod M)) mod M
• 나누기의 경우에는 성립하지 않는다. (Modular Inverse를 구해야 함)
• 뺄셈의 경우에는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야 한다.
• (A-B) mod M = ((A mod M) - (B mod M) + M) mod M

나머지 - 10430

Python 3

Java 8

• 문제에서 “정답을 ~~~로 나눈 나머지를 출력하라” 라는 말이 있는 이유는 정답이 int 나 long long과 같은 자료형의 범위를 넘어가기 때문이다.
• 앞에서 본 것처럼 매번 나누면 된다.

• (6 - 5) % 3 = 1 % 3 = 1 이다.
• (6 % 3 - 5 %3) % 3 = (0 - 2) % 3 = -2 % 3 = ? (-2 or 1)

• 음수의 경우 결과의 부호가 프로그래밍 언어마다 다르다.