[数据结构与算法]K倍区间(前缀和+同余)

题目描述

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

5 2
1
2
3
4
5

6

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k;
LL s[N], cnt[N];

int main() {
	scanf("%d%d", &n, &k);
	
	for (int i = 1; i <= n;i++) {
		scanf("%d", &s[i]);
		s[i] += s[i-1];
	}
	
	LL res = 0; 
	cnt[0] = 1; // // 第一次遇到区间和为0时，应该直接+1，s[i]=0指的是从1到i直接就是满足条件的
	for (int i = 1; i <= n; i++) {
		res += cnt[s[i]%k]; // 这个 s[i]%k 可以和前面取模为 s[i]%k的分别构成一个k倍区间
							// 所以此时又新增了cnt[s[i]%k]个K倍区间
		cnt[s[i]%k]++;
	}
	
	cout << res << endl;
	
	return 0;
}