[백준] / [Python] / [10986] 나머지 합

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

10986번: 나머지 합

---

문제

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

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

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

---

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

L = list(map(int, input().split()))
array = [0 for _ in range(N+1)] # 누적 합
res = [0] * M # 나머지 분류

for i in range(1, N+1):
    array[i] = L[i-1] + array[i-1]
    res[array[i-1] % M] += 1 # 누적 합을 M으로 나눈 나머지가 같은 것 끼리 분류

c = res[0]
for r in res:
    c += r * (r-1) // 2 # 분류 리스트에서 2개를 조합한 개수

print(c)

# L : 1, 2, 3, 1, 2
# array : 0, 1, 3, 6, 7, 9
# res : 3, 0, 2
# array(누적합) 에서 3으로 나누어 떨어지는 인덱스 : 1, 2, 4
# 1, 2, 4 중 2개를 택하면 택한 모든 구간은 3으로 나누어 떨어짐