[백준] 10986번 나머지 합 - python

문제 링크: https://www.acmicpc.net/problem/10986

10986번: 나머지 합

먼저 누적합을 구해줘야합니다. 그 다음 M으로 나누어 떨어지는 구간을 찾아야하는데 이 부분을 찾기 위해서 매번 구간을 정해서 구하게 되면 N = 10^6인 상태에서 O(N^2)이 되므로 시간 초과가 나게 됩니다.

 

그래서 다음과 같은 특성을 이용해야합니다. i ~ j 구간의 합을 구하게 되면 nums[i] - nums[j]가 되게 되는데 이것이 M의 배수가 되려면 nums[i]와 nums[j]를 M으로 나누었을 때의 같아야 합니다. (aM + 나머지) - (bM + 나머지) = (a - b)M이 되어야 하므로 누적합을 순차적으로 탐색하면서 현재 누적합의 나머지와 같은 누적합이 있다면 해당 구간의 합은 M의 배수가 됩니다.

 

# 문제 링크: https://www.acmicpc.net/problem/10986

import sys
from collections import defaultdict

input = sys.stdin.readline

n, m = tuple(map(int, input().split()))
nums = list(map(int, input().split()))

prefix = defaultdict(int)

answer = 0
for i in range(1, n):
    nums[i] += nums[i - 1]

for i in range(n):
    if nums[i] % m == 0:
        answer += 1
    answer += prefix[nums[i] % m]
    prefix[nums[i] % m] += 1

print(answer)