[python] 10986 - 나머지 합

10986번: 나머지 합 (acmicpc.net)

10986번: 나머지 합

 

부분합 문제이다.

이전까지의 부분합 개념을 이용하여 풀려고 했는데

계속 런타임 에러가 났다.

도저히 방법을 찾을 수가 없어 다른 풀이를 참고하여 해결하였다.

 

참고 사이트 : [파이썬] 백준 10986번 나머지 합 (tistory.com)

 

수학적 지식이 필요했는데,

간단하게 말하면 부분합을 구한 후 m으로 나누었을 때의 나머지가 동일한 구간을 찾으면 된다.

쉽게 이해하기 위해 그림으로 그려보았다.

 

 

우선 배열 [1,2,3,1,2]의 누적합 배열은 [1,3,6,7,9]이다.

m의 값이 3이라면

누적합 배열에서 각각의 원소를 3으로 나눈 나머지 배열은 [1,0,0,1,0]이다.

 

이 때, 나머지가 같은 부분합끼리 부분합을 구한다면

sum[i]-sum[i-1]의 연산을 거쳐야 하므로

연산 후 나머지는 0이 되고 결국 m으로 나누어 떨어지게 된다.

 

결론적으로 m으로 나누어 떨어지는 부분합은

나머지가 동일한 원소들 중에서 두개를 선택하는 경우의 수와 같다. (n*(n-1)//2)

(나머지가 0이라면 연산 전 부분합이 m으로 나누어 떨어지므로 계산에 포함시킨다.)

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
arr = list(map(int, input().split()))
sumL = [0]*(n+1)
cnt = [0]*(m+1)

for i in range(n):
    sumL[i+1] = (arr[i]+sumL[i])%m
    cnt[sumL[i+1]] +=1

ans = cnt[0]

for i in range(m+1):
    ans += (cnt[i]*(cnt[i]-1))//2
    
print(ans)