[Python] 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으로 나누어 떨어지는 구간의 개수를 출력한다.

해설

문제에 대해서 이해가 잘 안가서 나머지가 나오는 경우의 수가 중요하다는 질문 게시판 내용을 보고 힌트를 얻음

소스 코드

n, m = map(int, input().split())

seq = list(map(int, input().split()))

count = 0
num = 0

s_seq = {}
for i in range(n):
    num = (num + seq[i]) % m
    if num == 0:
        count += 1
    try:
        s_seq[num] += 1
    except:
        s_seq[num] = 1

for key, value in s_seq.items():
    if value >= 2:
        count += (value * (value-1)) / 2
print(int(count))