AcWing 1230. K倍区间

对于求区间的和，首先想到的就应该是用前缀和。

注：如果$S_i$ % $k$ $==a,S_j$ % $k==a$，则$(S_i-S_j)$ % $k==0$

假如现在对于一个右端点为$i$的区间，如果长度为$1$没那么就是$S_i$ - $S_{i-1}$,长度为二就是$S_i-S_{i-2}$，…长度为$i$就是$S_i-S_0$，如果问这些数理有多少是$k$的倍数，即求$S_0,S_1,S_2,......S_{i-1}$中有多少个数与$S_i$ $mod$ $k$的余数相同，即求$S_0$到$S_{i-1}$中与$S_i$ $mod$ $k$的余数相同的数出现了多少次，那么就可以直接用哈希表来存。

由于此题范围较小，所以可以直接用数组来模拟哈希表，用cnt[x]来求余数为$x$的数的个数。

#include
using namespace std;
const int N = 1e5 + 10;
#define ll long long

int n, k;
int cnt[N];
ll s[N];	//前缀和数组

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		s[i] += s[i - 1];
	}

	ll res = 0;
	cnt[0]++;	//s[0] % k = 0

	for (int i = 1; i <= n; i++) {
		res += cnt[s[i] % k];
		cnt[s[i] % k]++;	//这一步就使得i枚举到后边的时候，res加的时候不需要再重新算一遍前边的前缀和
	}
	cout << res;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27