Кратные отрезки

면접 대비

시간 제한1초메모리 제한1024 MB

요약

원소 합이 k로 나누어떨어지는 부분 배열의 개수를 구간 합의 나머지와 빈도 맵으로 센다.

난이도: 보통10점 중 4점
유형: 누적 합, 배열, 해시맵, 수학
정답자: 아직 제출이 없습니다

문제

Задан массив натуральных чисел $A = \[a\_1, a\_2, \ldots, a\_n]$ . Отрезком массива $A$ с $l$ по $r$ будем называть массив $\[a\_l, a\_{l+1}, \ldots, a\_r]$ .

Для заданного массива $A$ и числа $k$ требуется найти количество пар $(l, r)$ , таких что $l \le r$ и сумма чисел на отрезке массива $A$ с $l$ по $r$ делится на $k$ без остатка.

입력

На первой строке ввода заданы целые числа $n$ --- число элементов массива $A$ и $k$ ( $1 \le n \le 200\\,000$ , $2 \le k \le 10^9$ ).

На второй строке заданы целые числа $a\_1, a\_2, \ldots, a\_n$ --- элементы массива $A$ ( $1 \le a\_i \le 10^9$ ).

출력

Выведите одно число: количество пар $(l, r)$ , таких что $l \le r$ , и сумма чисел на отрезке массива $A$ с $l$ по $r$ делится на $k$ без остатка.

힌트

В примере подходят следующие отрезки:

$l = 1$ , $r = 3$ , отрезок $\[1, 2, 3]$
$l = 1$ , $r = 4$ , отрезок $\[1, 2, 3, 4]$
$l = 2$ , $r = 2$ , отрезок $\[2]$
$l = 2$ , $r = 5$ , отрезок $\[2, 3, 4, 5]$
$l = 3$ , $r = 5$ , отрезок $\[3, 4, 5]$
$l = 4$ , $r = 4$ , отрезок $\[4]$

예제1

예제 1
입력
```
5 2
1 2 3 4 5
```
예상 출력
```
6
```