K倍区间 C++

1230. K倍区间 - AcWing题库

一开始想到的用前缀和来做，时间复杂度为O(n^2),Time Limit Exceeded

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 100010;int n,k;
int s[N],a[N];int main() {cin >> n >> k;for (int i = 1;i <= n;i++) {scanf("%d",&a[i]);s[i] = s[i-1] + a[i];}int res = 0;for (int r = 1;r <= n;r++) {for (int l = 1;l <= r;l++) {int sum = s[r] - s[l-1];if (sum % k == 0) res++;}}cout << res << endl;
}

for (int l = 1;l <= r;l++) {
            int sum = s[r] - s[l-1];
            if (sum % k == 0) res++;
        }

这段代码中（s[r] - s[l-1]）% k == 0    ==>  s[r] %k == s[l-1]%k

当r固定时，我们只需要在1-r中找到有多少个是s[l-1]%k 的值和s[r] %k相等即可

将l-r =>0-(r-1),那么只需要在0-r中找到有多少个是s[l]%k 的值和s[r] %k相等即可

定义一个数组cnt用来存储对应s[l]%k余数的个数

即cnt[s[l]%k]的值为余数为s[l]%k的l个数(l为左端点)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;typedef long long LL;const int N = 100010;int n,k;
LL s[N],cnt[N];int main() {cin >> n >> k;for (int i = 1;i <= n;i++) {scanf("%lld",&s[i]);s[i] += s[i-1];}LL res = 0;cnt[0] = 1;for (int r = 1;r <= n;r++) {res += cnt[s[r]%k];cnt[s[r]%k]++;}cout << res << endl;
}

为什么cnt[0]要设为1

因为如果不需要左端点，该区间即可符合条件，那么res应该+1