PRE504 余数相同的区间

难度梯度：T3｜训练重点：前缀余数计数

题目描述

给定 N 个整数 a_i 和正整数 M，求元素和能被 M 整除的非空连续子数组个数。数组元素可能为负。

求和可以为负数或 0；只要该和是 M 的整数倍，就满足条件。不同端点对应不同区间。

输入格式

第一行 N M；第二行 N 个整数 a_i。

输出格式

输出满足要求的区间数量。

样例输入

5 3
1 2 3 4 2

样例输出

7

样例说明

前缀余数相同的一对端点对应一个区间。

数据范围

1≤N,M≤2×10^5；-10^9≤a_i≤10^9。

子任务

30 分：N≤2000；30 分：全为正数；40 分：无附加限制。