蓝桥杯算法题：K倍区间

给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出

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

示例

输入：
5 2
1
2
3
4
5

输出：
6

思路：先用前缀和来快速计算区间的和， 这道题的N是10^5量级的，两层循环就会爆，所以要考虑如何压缩，我看了下网友的解法，感觉很妙，比如说有两个区间，[1,a]和[1,b]，如果[1,a]区间和为sum1，[1,b]区间和为sum2，且sum1%k==sum2%k，那么（sum2-sum1）%k是不是就等于0，对应的，区间[a+1,b]的和就是（sum2-sum1），是不是就整除k，也就是k倍区间，所以可以维护一个数组cnt，cnt[i]表示对k取模余数为i的区间数，如果有两个区间对k取模一样，那么他们可以生成一个被k整除的区间

代码如下：

#include <iostream>
using namespace std;
long long pre[100010];
int cnt[100010];
int main()
{
  int n,k;
  cin>>n>>k;
  long long res=0;
  cnt[0]=1;//为什么cnt[0]要为1，因为刚好被k整除，要特殊处理，代入pre[0]=k理解即可，此时要是cnt[0]=0，那么res就增加了0，不符合实际
  for(int i=1;i<=n;i++){
    cin>>pre[i];
    pre[i]=pre[i]+pre[i-1];//自己进行前缀和
    res+=cnt[pre[i]%k];
    cnt[pre[i]%k]++;
  }
  cout<<res<<endl;
  return 0;
}