[백준 10986] 나머지 합

	# 백준 10986번 문제검색 링크 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net

 

Key Point

• (A+B)%C는 ((A%C)+(B%C))%C와 동일하다 결국 이 말은 특정 구간의 나머지 연산을 더해 구한 값과 구간합의 나머지 연산의 결과는 동일하다는 것이다
• 합배열 (sum[j]-sum[i])%M 은 결국 sum[j]%M - sum[i]%M과 동일함으로 결국 sum[j]%M=sum[i]%M의 결과가 나오게 된다 즉 합배열간 나머지가 동일한 것의 조합을 더해주면 된다.
• 기본적으로 구간합이 나머지가 0인경우도 더해준다

 

문제 코드

 

import sys
input=sys.stdin.readline

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

numbers=list(map(int, input().split()))
sum_array=[0]
answer=0
chk=[0]*M #같은 나머지수 카운트를 위한 배열 

for i in numbers: #합배열 만들기
    tmp=sum_array[-1]
    sum_array.append(tmp+i)
    
del sum_array[0] #첫번째는 임의로 0으로 만들었기 때문에 삭제

for i in sum_array: #기본적으로 나머지가 0인 합배열 더해주고 같은 나머지수 카운트
    if i%M == 0:
        answer+=1
    chk[i%M]+=1
    
for i in range(M): #같은 나머지수끼리 조합하여 계산
    if chk[i]>1:
        answer+=chk[i]*(chk[i]-1)//2
    
    
print(answer)