[BOJ] 10986번 나머지 합

누적합을 빠르게 구하는 방법을 이용하고, 이중 for문을 통해 모든 가능한 i,j에 대해 체크하면 시간초과가 발생한다.

import sys
input = sys.stdin.readline

N,M = map(int, input().split())
nums = list(map(int,input().split()))
cumulative_sum = [0]

for i,num in enumerate(nums):
  cumulative_sum.append(cumulative_sum[i]+num)

ans = 0
for i in range(1,len(nums)+1):
  for j in range(i,len(nums)+1):
    now_cumulative_sum = cumulative_sum[j]-cumulative_sum[i-1]
    if now_cumulative_sum%M==0:
      ans+=1

print(ans)

따라서 다른 방법을 이용해야 하는데,
(a + b) % MOD = (a % MOD + b % MOD) % MOD
를 생각하여 접근해야 한다.

구간합에 따른 나머지들을 구한 뒤, 나머지가 같은 곳 끼리 뺀 구간은 M으로 나눠 떨어진다.
또 구간합 자체의 나머지가 0이면 그 구간 자체도 해당이 된다.

import sys
input = sys.stdin.readline

from collections import Counter

N,M = map(int, input().split())
nums = list(map(int,input().split()))
cumulative_sum = [0]

for i,num in enumerate(nums):
  cumulative_sum.append((cumulative_sum[i]+num)%M)

ans = 0
for k,v in Counter(cumulative_sum[1:]).most_common():
  if k==0: # 나머지가 0이면 혼자서도 나눠떨어짐
    ans += v
  ans += (v*(v-1)) // 2 #나머지가 같은 곳들 중 2개 선택

print(ans)