k倍区间（前缀和）

k倍区间-第八届蓝桥省赛-B组

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？
输入格式:

第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

1≤N,K≤100000 , 1≤Ai≤100000
输出格式:

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

5 2
1
2
3
4
5

输出样例:

在这里给出相应的输出。例如：

6
解题思路：
利用前缀和，可以求出[ l , r ]区间的所有数值和sum[ r ]-sum[ l-1 ]，如果(sum[ r ]-sum[ l-1 ])%k=0,即
该区间符合条件，其中(sum[ r ]-sum[ l-1 ])%k=0可以化为sum[ r ]%k=sum[ l-1 ]%k,所以可以将判断条件变为，sum[ i ]对k取模后，统计每一种结果的数量；最后求每一种结果的可形成的组合数 C ( x , 2 )之和，再加上sum[ i ]%k=0的种类数就行了;

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include