나머지 연산 · 알고리즘 노트

개념

나머지 연산은 정수를 일정한 크기로 묶고 남는 값을 구합니다. $17$ 을 $5$ 개씩 묶으면 $2$ 가 남으므로 $17\bmod5=2$ 입니다. 세 언어 모두 정수의 나머지 연산에 %를 사용합니다.

이 문서에서는 기준이 되는 수 $M$ 을 양의 정수로 둡니다. $A\ge0$ 이면 나머지는 $0$ 이상 $M$ 미만입니다. 특히 $A\bmod M=0$ 이면 $A$ 는 $M$ 의 배수입니다.

계산	C++	Java	Python
나머지 구하기	`17 % 5` → 2	`17 % 5` → 2	`17 % 5` → 2
배수 확인	`a % m == 0`	`a % m == 0`	`a % m == 0`
짝수 확인	`a % 2 == 0`	`a % 2 == 0`	`a % 2 == 0`

구한 나머지에 같은 나머지 연산을 다시 적용해도 값은 같습니다. 예를 들어 $(17\bmod5)\bmod5=2$ 입니다. 이미 $0$ 부터 $M-1$ 사이의 값으로 줄였기 때문입니다.

C++과 Java의 % 결과는 $0$ 이거나 왼쪽 피연산자와 같은 부호입니다. Python은 기준 $M$ 이 양수이면 결과가 항상 $0$ 이상입니다.

계산	C++	Java	Python
음수의 나머지	`-7 % 3` → -1	`-7 % 3` → -1	`-7 % 3` → 2
음이 아닌 나머지	`r = a % m;` 이후 `r < 0`이면 `r += m;`	`Math.floorMod(a, m)`	`a % m`

나머지가 음수이면 $M$ 을 한 번 더해 $0$ 이상 $M$ 미만으로 맞출 수 있습니다. 예를 들어 C++에서 $-7\bmod3$ 의 결과 $-1$ 에 $3$ 을 더하면 $2$ 입니다. 순환하는 위치나 배열 인덱스를 구할 때는 이 범위의 값을 사용합니다.

$2,7,12,17$ 은 모두 $5$ 로 나눈 나머지가 $2$ 입니다. 두 수의 차이가 $M$ 의 배수이면 $M$ 으로 나눈 나머지가 같습니다. 이러한 관계를 합동이라고 하며 $a\equiv b\pmod M$ 으로 표시합니다.

$0,1,2,3,4$ 번 위치를 순환한다고 하겠습니다. 현재 위치가 $4$ 일 때 세 칸 이동한 위치는 $(4+3)\bmod5=2$ 입니다. 한 바퀴에 해당하는 $5$ 칸을 더 이동해도 도착 위치가 같으므로 이동 횟수를 나머지로 줄일 수 있습니다.

아래의 $\bmod M$ 은 $0$ 이상 $M$ 미만으로 맞춘 나머지를 뜻합니다.

(a+b)\bmod M=((a\bmod M)+(b\bmod M))\bmod M

(a-b)\bmod M=((a\bmod M)-(b\bmod M))\bmod M

(ab)\bmod M=((a\bmod M)(b\bmod M))\bmod M

각 수에서 $M$ 의 배수인 부분을 빼도 나머지는 같습니다. 두 수를 더하거나 빼면 이 부분도 $M$ 의 배수로 남습니다. 곱셈에서도 $a=qM+r$ , $b=pM+s$ 로 쓰면 $ab=qpM^2+(qs+pr)M+rs$ 이므로 $rs$ 의 나머지만 구하면 됩니다.

$M=5$ , $a=17$ , $b=9$ 이면 두 나머지는 각각 $2,4$ 입니다.

여러 수의 합이나 곱도 계산할 때마다 나머지를 취할 수 있습니다. 거듭제곱 역시 곱셈을 반복하므로 같은 성질을 적용합니다. 다만 %는 곱셈이 끝난 뒤 적용되므로, 중간 곱이 자료형 범위 안에 들어가는지 확인해야 합니다.

나머지는 수의 크기 순서를 보존하지 않습니다. $9<12$ 이지만 $9\bmod5=4$ 는 $12\bmod5=2$ 보다 큽니다. 최댓값이나 최솟값을 비교할 때는 원래 값을 기준으로 판단합니다.

예제 범위의 정수 연산을 기준으로 합니다.

연산	시간복잡도	공간복잡도
나머지 계산과 음수 보정	$O(1)$	추가 $O(1)$

정수 $A$ 와 양의 정수 $M$ 이 주어진다. $A$ 를 $M$ 으로 나눈 나머지를 $0$ 이상 $M$ 미만의 값으로 구하여라.

첫째 줄에 정수 $A$ 와 양의 정수 $M$ 이 공백을 사이에 두고 주어진다. $-9\,999\le A\le9\,999$ ; $1\le M\le100$ 이다.

구한 값을 출력한다.