10986번 - 나머지 합

문제

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

10986번: 나머지 합

풀이

구간합이 M으로 나누어 떨어지려면, 슬라이딩 윈도우를 이용하되 A[i]와 A[j]의 M으로 나누었을 때 나머지가 서로 같아야 한다. 예를 들어 어떤 수 a와 b가 각각 a = 3*n + 1, b = 3*m + 2 라고 할 때, a-b = 3*(n+m) - 1로 3으로 나누어 떨어질 수 없다. a = 3*n + 1, b = 3*n + 1 이라면 가능하다. 이러한 점을 고려하여 M으로 나누었을 때 나머지가 같은 것의 개수 중 두 개씩 고르는 경우의 합이 답이 될 것이다.

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
A = [0] + list(map(int,input().split()))

dp = [0]*(10**6+1)
dp[1] = A[1]

table = [0]*M
table[0] += 1
r = dp[1]%M
table[r] += 1

for i in range(2,N+1):
    dp[i] = dp[i-1] + A[i]
    r = dp[i]%M
    table[r] += 1
    
print(sum(map(lambda x : x*(x-1)//2, table)))