백준 3673 나눌 수 있는 부분 수열

배열의 누적합을 구하고 그 누적합의 나머지를 저장한다.

나머지가 같은 구간을 처리하는 것이 문제 핵심

서로 다른 두 구간을 선택 nC2 이다.

T = int(input())

for _ in range(T):
    division, N = map(int, input().split())
    arr = [0] + list(map(int, input().split()))
    len_arr = len(arr)
    prefix = [0 for _ in range(N+1)]
    nameoji = {}
    ans = 0
    for i in range(1, len_arr):
        prefix[i] = prefix[i-1] + arr[i]
        idx = prefix[i]%division
        nameoji[idx] = nameoji.get(idx, 0) + 1

    for key in nameoji.keys():
        ans += nameoji[key]*(nameoji[key]-1)//2

    ans += nameoji.get(0, 0)
    print(ans)