python 백준 10986 나머지 합

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

누적합

• 값들을 누적해 가며 기록(total)
• 누적할때 나머지 값만 중요하므로 M으로 나머지 연산하며 누적
• 각각의 지점에서 total 값이 얼마인지를 기록(cnt)

로직

• 첫 숫자 값 1이라고 가정
• x번 index까지 누적된 값이 1이라면
• 0-x번 사이의 누적합이 M으로 나누어 떨어짐 => 1번-x번 사이의 합이 M로 나누어 떨어짐
• 즉 0번 index에서 total = 1 이라면, x번 index에서 total = (A * M) % M + 1 = 1
• 2-x번 사이의 합은 (A*M) => M으로 나누어 떨어짐
• 이렇게 만들 수 있는 지점의 조합의 수가 정답
• 따라서 cnt[idx] 값이 같은 지점의 조합의 수가 정답(comb(v,2))

from math import comb
def solution(M:int,nums:list[int])->int:
    total = 0
    cnt = [0]*M
    cnt[0] = 1
    for num in nums:
        total = (total+num)%M
        cnt[total] += 1
    value = 0
    for v in cnt:
        value += comb(v,2)
    return value

N,M = map(int,input().split())
nums = list(map(int,input().split()))
ans = solution(M,nums)
print(ans)