1230.K倍区间
思路
从暴力开始逐步优化,暴力需要 的复杂度,通过前缀和可以减少到 。因为倍数关系,可以直接存下对应 k 倍的前缀和数组的元素,也就是某一个边界内的元素和,这样就可以不用遍历 l 和 r 了。
- 因为我只需要找倍数为 k 的,那么只要 s[l] 和 s[r] 是 k 倍就行,也就是模 k 得 0
- 因为 ,所以只要分别成倍数即可
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int n, k;
ll sum[N], a[N];
ll cnt[N]; // 表示余数是 i 的数有多少个
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
ll res = 0;
cnt[0] = 1;
// 没必要左右区间遍历,这样根暴力没区别了 O(n^2)
// for (int i = 1; i <= n; i++) {
// for (int j = i; j <= n; j++) {
// if ((sum[j] - sum[i - 1]) % k == 0) res ++;
// }
// }
// 使用以下做法,因为我只需要找倍数为k的,那么只要s[l]和s[r]是k倍就行,也就是模k得0
// 因为 k * (s[r] - s[l - 1]) = k * s[r] - k * s[l - 1],所以只要分别成倍数即可
for (int i = 1; i <= n; i++) {
res += cnt[sum[i] % k];
cnt[sum[i] % k] ++;
}
cout << res << endl;
return 0;
}