나머지 합

1. 개요

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

2. 풀이

import sys
from collections import deque

def solution():
    # 입력함수
    INPUT = lambda: sys.stdin.readline().rstrip()
    READINT = lambda: int(INPUT())
    READINTLIST = lambda: list(map(int, INPUT().split()))

    (N, M), NUMS = READINTLIST(), READINTLIST()

    sum = 0
    
    # 나머지가 몃일때의 누적합의 갯수를 기록
    numRemainder = [0] * M

    for i in range(N):
        sum += NUMS[i]
        numRemainder[sum % M] += 1

    # 나머지가 0인것들을 추가
    result = numRemainder[0]

    # 나머지가 같은것들을 2개뽑으면 가능
    for i in numRemainder:
        result += i*(i-1)//2
  
    return result
print(solution())