k倍区间

题目描述

给定一个长度为 $N$ 的数列， $A_1, A_2, \cdots A_N$。如果其中一段连续的子序列 $A_i, A_{i+1}, \cdots A_j (i \le j)$ 之和是 $K$ 的倍数，我们就称这个区间 $[i, j]$ 是 K 倍区间。
你能求出数列中总共有多少个 $K$ 倍区间吗？

输入描述

第一行包含两个整数 $N$ 和 $K$ $(1 \le N, K \le 10^5)$。
以下 $N$ 行每行包含一个整数 $A_i$ $(1 \le A_i \le 10^5)$。

输出描述

输出一个整数，代表 K 倍区间的数目。

输入输出样例

示例
输入


5 2
1
2
3
4
5

输出


6

8

  • 前缀和：计算数组的前缀和 $S$。
  • 同余定理：如果区间 $[i, j]$ 的和是 $K$ 的倍数，即 $(S_j - S_{i-1}) \% K == 0$，这意味着 $S_j \% K == S_{i-1} \% K$。
  • 转化：只需要计算前缀和模 $K$ 的余数。如果有 $c$ 个前缀和的余数相同（比如都是 1），那么从这 $c$ 个位置中任选 2 个（$C_c^2$），它们之间的区间和就是 $K$ 的倍数。

```cpp

include

include

using namespace std;
int main()
{
int N,K,sum=0;
cin>>N>>K;
vectorarr(N+1,0);
vectorcnt(K,0);
for(int i=1;i<=N;i++)
cin>>arr[i];
for(int i=1;i<=N;i++)
arr[i]=(arr[i-1]+arr[i])%K;
for(auto &x:arr)
cnt[x]++;
for(auto &c:cnt)
sum+=(c-1)*c/2;
cout<<sum;
}