[10986] 나머지 합 (합배열)

10986번: 나머지 합

 

분석

• (A+B)%C = ((A%C)+(B%C))이므로 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일
• 구간 합 배열을 이용한 식 S[i]-S[j]는 원본 리스트의 j+1부터 i까지의 구간 합이므로 합배열의 나머지 값이 같으면 두개 뽑아서 합배열 값-합배열 값으로 나누어떨어지는 구간 찾을 수 있음
• S[i]%M의 값과 S[j]%M의 값이 같다면 (S[i]-S[j])%M은 0이므로 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[i], S[j]가 같은 (i, j)쌍을 찾으면 원본 리스트에서 j+1부터 i까지의 구간합이 M으로 나누어 떨어짐

풀이

import sys
input=sys.stdin.readline

n,m=map(int, input().split())
# 입력 리스트
a=list(map(int, input().split()))

# 합배열
s=[0]*n
s[0]=a[0]
for i in range(1,n):
    s[i]=s[i-1]+a[i]

c=[0]*m # 같은 나머지의 인덱스 카운트
# 합배열의 나머지 값이 같으면 두개 뽑아서 합배열값-합배열값으로 나누어떨어지는 구간 찾을수 할 수 있음

cnt=0
for i in range(n):
    k=s[i]%m # 합배열 값을 m으로 나눈 나머지
    if k==0: # 합배열 값(0~i까지 합)이 m으로 나누어떨어짐
        cnt+=1
    c[k]+=1

for i in range(m):
    if c[i]>1:
        cnt+= (c[i]*(c[i]-1)//2) # iC2 : 2가지를 뽑는 경우의 수를 정답에 더함

print(cnt)