k倍区间c++
题目
输入样例：
5 2
1
2
3
4
5
输出样例：
6思路
本题默认所有读者已经理解了如何求前缀和。
可以利用双层循环分别枚举左端点和右端点即可枚举完所有区间，而对于每个区间，利用一维前缀和判断它是否是一个k倍区间，是的话答案数+1，但时间复杂度为O(10^10)，超时。代码如下：
//s[]为前缀和数组, res 为总区间数
for (int r = 1; r <= n; r ++)
for (int l = 1; l <= r; l ++)
{if ((s[r] - s[l - 1]) % k == 0)res ++;
}
实际上，这个双层循环可以理解为，在右端点r固定，l 在 0 ~ r - 1 之间变化的情况下，可以找到多少个满足 (s[r] - s[l]) % k == 0的区间，判断条件变换一下得：(s[r] % k - s[l] % k) % k == 0，即在 0 ~ r - 1 之间能找到有多少个s[l] % k 等于 s[r] % k，使得[l, r]构成k倍区间。而 s[r] % k的个数可以在r从前往后遍历过程中用一个数组cnt统计出来，cnt[i]代表 s[r]%k余数等于i的个数。
特别注意，当s[i] % k 等于0时，说明s[i]本身即可构成一个k倍区间，因此cnt[0]要预置为1，这样当遇到第一个s[i] % k==0时就可以统计到答案res中去了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N], cnt[N];int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n, k;cin >> n >> k;//求前缀和for (int i = 1; i <= n; i ++){cin >> a[i];a[i] += a[i - 1];}LL res = 0;cnt[0] = 1;for (int i = 1; i <= n; i ++){res += cnt[a[i] % k] ++;}cout << res;return 0;
}