P8649 [Lanqiao Cup 2017 NOI Qualifier B] K-Multiple Intervals

Given a sequence of length $N$, $A_1, A_2, \cdots A_N$. If the sum of a consecutive subsequence $A_i, A_{i+1}, \cdots A_j (i \le j)$ is a multiple of $K$, then we call the interval $[i, j]$ a $K$-multiple interval. Can you find how many $K$-multiple intervals there are in the sequence?

The first line contains two integers $N$ and $K$ $(1 \le N, K \le 10^5)$. The next $N$ lines each contain one integer $A_i$ $(1 \le A_i \le 10^5)$.

Output one integer, representing the number of $K$-multiple intervals.

Time limit: 2 seconds, 256M. The 8th Lanqiao Cup 2017. Translated by ChatGPT 5