liên tiếp có tổng chia hết cho k (chiak.*)

Cho số nguyên dương \(n\) và dãy số \(a\) gồm \(n\) số nguyên \(a_{1},\ a_{2},\ ...,\ a_{n}\). Một dãy con liên tiếp của dãy số \(a\) có dạng \(a_{i},\ a_{i + 1},\ \ldots,\ a_{j}\) với \(1\ \leq \ i\ \leq \ j\ \leq \ n\), tổng của dãy con liên tiếp \(a_{i},\ a_{i + 1},\ \ldots,\ a_{j}\) là \(a_{i}\ + \ a_{i + 1}\ + \ \ldots\ + \ a_{j}\).

Em hãy đếm số lượng dãy con liên tiếp của dãy số \(a\) đã cho có tổng các phần tử của dãy con này chia hết cho số nguyên dương \(k\).

Dữ liệu vào:

- Dòng 1 ghi 2 số nguyên dương \(n\) và \(k\ (n \leq 10^{6},\ k\ \leq \ 10^{9})\). Các số trên cùng một dòng cách nhau ít nhất một khoảng trống;

- Dòng 2 ghi lần lượt các số nguyên \(a_{1},\ a_{2},\ ..,\ a_{n}\ (|a_{i}|\ \leq \ 10^{9},\ i = 1..n)\). Các số trên cùng một dòng cách nhau ít nhất một khoảng trống.

Kết quả:

+ Một số duy nhất là số lượng dãy con có tổng các phần tử chia hết cho \(k\).

Ví dụ:

Giới hạn:

- Có 5/25 test có \(n\ \leq \ 10^{2}\);

- Có 15/25 test có \(10^{2} < n \leq 10^{3}\);

- Có 5/25 test có \(10^{3} < n\ \leq \ 10^{6}\).