Skip to main content

1230.K倍区间

tip

原题链接：https://www.acwing.com/problem/content/description/1232/

思路​

从暴力开始逐步优化，暴力需要 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[l−1])=k∗s[r]−k∗s[l−1]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;
}