Skip to main content

1230.K倍区间

思路

从暴力开始逐步优化,暴力需要 O(n3)O(n^3) 的复杂度,通过前缀和可以减少到 O(n2)O(n^2)。因为倍数关系,可以直接存下对应 k 倍的前缀和数组的元素,也就是某一个边界内的元素和,这样就可以不用遍历 l 和 r 了。

  • 因为我只需要找倍数为 k 的,那么只要 s[l] 和 s[r] 是 k 倍就行,也就是模 k 得 0
  • 因为 k(s[r]s[l1])=ks[r]ks[l1]k * (s[r] - s[l - 1]) = k * s[r] - k * s[l - 1],所以只要分别成倍数即可

代码

#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;
}