蓝桥杯2017年第八届真题-k倍区间 （C++代码）

        前缀和对 K 取模，统计答案的时候就是前面有多少个前缀和与该位置前缀和 % K 下相等，这样相减之后这些区间和 % K 下等于 0，也就是 K 的倍数了，我用分块来维护（数据结构学傻了，其实只需要开一个桶统计一个位置加入一个计数就可以了。

参考代码:

#ifndef LOCAL
	#include <bits/stdc++.h>
#endif
constexpr auto Inf = 0X3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != 'C' && o != 'D'); return o;
	}
}
using namespace IO;

const int SIZE = 1E5 + 7;
int pre[SIZE], Arr[SIZE], N, K, bS;
int BeL[SIZE], e[322][SIZE];

int Ask(int pos, int w) {
	int res = e[BeL[pos] - 1][w];
	for (int L = bS * (BeL[pos] - 1) + 1; L < pos; L++)
		res += pre[L] == w;
	return res;
}

int main() {
	N = read(), K = read(), bS = sqrt(N);
	for (int pos = 1; pos <= N; pos++)
		BeL[pos] = (pos - 1) / bS + 1,
		Arr[pos] = read(), pre[pos] = (pre[pos - 1] + Arr[pos]) % K;
	/*for (int pos = 1; pos <= N; pos++)
		printf("%d ", pre[pos]); puts("");*/

	for (int pos = 1; pos <= BeL[N]; pos++) {
		for (int u = 0; u < K; u++)
			e[pos][u] = e[pos - 1][u];
		/*printf("L = %d, R = %d\n", bS * (pos - 1) + 1, min(bS * pos, N));*/
		for (int L = bS * (pos - 1) + 1, R = min(bS * pos, N); L <= R; L++)
			e[pos][pre[L]]++;
	}
	/*for (int pos = 1; pos <= BeL[N]; pos++, puts(""))
		for (int u = 0; u < K; u++)
			printf("%d ", e[pos][u]);*/

	LL ans = 0;
	for (int pos = 1; pos <= N; pos++)
		ans += Ask(pos, pre[pos]), ans += pre[pos] == 0;
	printf("%lld\n", ans);
}
/*
5 2
1 2 3 4 5

*/