[백준] 10986번: 나머지 합

문제

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

풀이

누적합을 사용해 풀었습니다.

ramainder에 누적합의 나머지 개수를 저장합니다.

\(_{i}{C}_{2}\) 를 계산해 answer에 더합니다.

 

코드

파이썬

import sys

input = sys.stdin.readline

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

total = 0
remainder = [0] * M
for i in range(N):
    total += A[i]
    remainder[total % M] += 1

answer = remainder[0]
for i in remainder:
    answer += (i * (i-1)) // 2

print(answer)