[백준 python 10986] 나머지 합

[Gold III] 나머지 합 - 10986

문제 링크

성능 요약

메모리: 157276 KB, 시간: 824 ms

분류

수학, 누적 합

제출 일자

2026년 1월 19일 15:27:02

문제 설명

수 N개 A₁, A₂, ..., A_N이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, A_i + ... + A_j (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10⁶, 2 ≤ M ≤ 10³)

둘째 줄에 N개의 수 A₁, A₂, ..., A_N이 주어진다. (0 ≤ A_i ≤ 10⁹)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

소스 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
s = [0] * n
c = [0] * m
s[0] = a[0]
cnt = 0

for i in range(1, n):
    s[i] = s[i-1] + a[i]

for i in range(n):
    remainder = s[i] % m
    if remainder == 0:
        cnt += 1
    c[remainder] += 1

for i in range(m):
    cnt += (c[i] * (c[i] - 1) // 2)

print(cnt)

연속된 구간의 합을 M으로 나누었을 때 0으로 나누어 떨어지는 것의 개수를 구하는 것이다.

해당 문제의 핵심 아이디어는 `(A + B) % C`는 `((A % C) + (B + C)) % C`와 같다는 것을 이용하는 것이다.

그렇다면 특정 구간의 합을 구하는 공식은 `S[i] - S[j]`이다.

`S[i] % M`의 값과 ` S[j] % M `의 값이 같다면 `(S[i] - S[j]) % M`도 같고 0으로 나누어 떨어진다.

그래서 구간합 배열을 만들고 그 구간합에 M을 나눈 나머지 배열을 만들어 준다.

나머지 배열에 0이면 나누어 떨어지기 때문에 0의 개수를 세어준다.

그리고 나머지 배열에서 같은 값을 찾아 2개를 뽑아 빼주면 그 구간도 0으로 나누어 떨어지는 조합이다.

이를 구현하기 위해서는 조합이 필요하다.