题目描述
给定一个长度为 N 的数列，A₁,A₂,⋯,A_N，如果其中一段连续的子序列 Aᵢ,A_{i+1},⋯,Aⱼ（i≤j）之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？

输入描述
第一行包含两个整数 N、K（1 ≤ N,K ≤ 10⁵）。
以下 N 行每行包含一个整数 Aᵢ（1 ≤ Aᵢ ≤ 10⁵）

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

输入输出样例
示例
输入

5 2
1
2
3
4
5

6

运行限制
最大运行时间：2s
最大运行内存: 256M

这道题一看可以使用暴力枚举，枚举的过程也是很简单的，就是跑N个循环，每一个循环分别从1~N中开始，当sum与K的余数为0时，那么sum就是K的倍数，区间i到j就是K倍区间，但是如果你实际使用这种代码（如下显示）

#include <stdio.h>
long long int list[100000];
int main(void)
{
	long long int n,k,i;
	scanf("%lld %lld",&n,&k);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&list[i]);
	}
	
	long long int sum,count,x,y;
	sum = count = 0;
	for(x=0;x<n;x++)
	{
		sum = list[x];
		for(y=x+1;y<n;y++)
		{
			sum += list[y];
			if(sum%k==0) count++;
		}
	}
	for(x=0;x<n;x++)
	{
		if(list[x]%k==0) count++;
	}
	printf("%lld",count);
	return 0;
}

就会发现，当N的值非常大，假如是10⁵量级，那么时间复杂度O(n^2)（通常两层循环为平方）将会达到100亿级别，这显然会超时，所以暴力枚举的方法不可用。

需要使用前缀和 + 同余计数 O (n) 的做法

名词解释：

前缀和定义

₀ = 0

S₁ = A₁

S₂ = A₁+A₂

Sⱼ = A₁+A₂+⋯+Aⱼ
区间 [i,j] 的和 = Sⱼ − S_{i−1}

我们需要的是Sⱼ − S_{i−1}是K的倍数，也就是(Sⱼ − S_{i−1})%k=0

又有余数公式：(a−b) % k = [(a % k)−(b % k)] % k 证明:证明过程

所以：[(Sⱼ mod k) − (S_{i−1} mod k)] mod k = 0 也就是两个数相减的时候的取余相等

那就是当(Sⱼ mod k)  =  (S_{i−1} mod k)的时候相等

综上，如果前缀和的余数相等，那么j和i-1的这两个区间的和（Sⱼ − S_{i−1}）就是k的倍数，也就是题目所要求的

如 k=2，S₂=3，S₀=0
3 mod 2 = 1，0 mod 2 = 0 → 余数不等，不是合法区间

我们可以使用一个数组来存放出现的余数的余数r的次数，如遇到余数r,则cnt[r] ++;

当我们走到 Sj，算出余数 r：

• 前面已经有 cnt[r] 个 S_{i-1} 和它余数一样
• 每一个都能和它凑出一个合法 K 倍区间
• 所以 ans +=cnt[r]然后再把当前这个余数 r 登记进去cnt[r]++

一开始 cnt[0]=0, S0=0，余数 0，它是最开头的前缀和，要先算进去。

#include <stdio.h>
long long cnt[100010]; // cnt[r] 记录余数r出现多少次
int main(void)
{
    int n, k;
    scanf("%d %d", &n, &k);
    long long sum = 0;
    long long ans = 0;
    cnt[0] = 1;   // S0=0，余数0一开始就有1个
    for(int i = 1; i <= n; i++)
    {
        long long a;
        scanf("%lld", &a);
        sum += a;
        int r = sum % k;
        ans += cnt[r];
        cnt[r]++;
    }
    printf("%lld\n", ans);
    return 0;
}