Задача: Кратные отрезки
Задан массив натуральных чисел \(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]\)
Ваш ответ: