[수학][mod] % 나머지 연산자

[수학][mod] % 나머지 연산자

나머지 연산

% 또는 mod(모드) 연산자 라고 한다.

나머지 연산자는 나눗셈 연산 후 나머지를 구하는데 사용한다.

나머지 연산의 특성상 결과값은 0 ~ (자신 - 1) 의 값이 나온다.

나머지 연산자의 분배 법칙을 보자.

각각 나머지 연산을 취한 후 다시 전체적으로 나머지 연산을 한다.

일단, 나누기의 경우에는 성립하지 않는다. (Modular Inverse를 구해야 한다.)

뺄셈의 경우, 음수가 나올 수 있기 때문에 M을 더해준 후 다시 전체의 나머지 연산을 해주어야 한다.

이는 C 언어의 % 연산자에서 음수 처리는 다음과 같이 정의되어 있기 때문이다.

X % Y를 연산할 때 그 연산 결과의 부호는 X의 부호를 따라간다.

Y의 부호는 무시되며, 오직 X가 양수이면 결과도 양수, X가 음수이면 결과도 음수라는 것이다.

일단 부호가 모두 양수라고 가정하고 계산을 한 후 앞 수의 부호를 붙이는 것이다.

예를 들어) 

1.   5 %  2 =  1

2.  -5 %  2 = -1

3.   5 % -2 =  1

4.  -5 % -2 = -1

의 결과를 볼 수 있다.

또한, 추가적으로 나머지 연산은 실수형에서는 동작하지 않는다. (컴파일이 되지 않는다.)

나머지 연산자 알고리즘 문제 : https://www.acmicpc.net/problem/10430

[참고] http://andyader.blogspot.kr/2013/08/c_27.html