[수학1]나머지 연산

• 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M 으로 나눈 나머지를 출력하라는 문제가 등장한다.
• (A +B ) mod M = ((A mod M) + (B mod M)) mod M
• (A x B) mod M = ((A mod M) x (B mod M)) mod M
• 나눈 기의 경우에는 성립하지 않는다. (Modular Inver 를 구해야 함)
• 뺄셈의 경우에는 먼저 mod 연산을 한 결과가 음수가 나눌 수 있기 때문에 다음과 같이 해야 한다.
• (A-B) mod M = ((A mod M ) - (B mod M)+M)mod M
  • ex ) (6-5)%3 = 1%3=1 이다
  • ex) (6%3 - 5%3)%3 = (0 - 2)%3 = -2 %3 = ? -- 음수의 경우 결과의 부호가 프로그래밍 언어마다 다르다.

• 0≤a%c <c
• 0≤b%c <c 이기 때문에
• (a%c ‒ b%c)의 결과는 -c<(a%c ‒ b%c)<c를 만족한다.
• 따라서, (a%c ‒ b%c +c) 는 0보다 큰 값을 갖기 때문에, 이 상태에서 다시 c로 나눠주면 원하는
결과를 얻을 수 있다.

 

 

https://www.acmicpc.net/problem/10430