https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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]
answer = 0
for i in range(1,n):
s[i] = s[i-1] + a[i]
for i in range(n):
temp = s[i]%m
if temp == 0:
answer+=1
c[temp]+=1
for i in c:
answer += i*(i-1)//2
print(answer)
|
cs |