K倍区间

acwing 1230

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;

typedef long long ll;

int n, k;
ll s[N]; //前缀和数组
ll cnt[N]; //cnt[i]表示模k余数为i的s[i]的个数

int main()
{
cin >> n >> k; //数组长度,以及k
for(int i = 1; i <= n; i++)
{
scanf("%lld", &s[i]);
}

for(int i = 1; i <= n; i++)
{
s[i] += s[i-1]; //计算前缀和
}

ll maxk = 0; //k倍区间个数


//为降低时间复杂度,将s[r] - s[l-1])%k == 0 转化为 s[r]%k == s[l-1]%k
cnt[0] = 1;
for(int i = 1; i <= n; i++)
{
maxk += cnt[s[i]%k]; //先累加 某个数%k 与 s[i]%k相等的值
cnt[s[i]%k]++; //更新(加入当前循环的结果)取余为 s[i]%k 的值的个数
}

cout << maxk << endl;


return 0;
}

最难理解的莫过于最后的循环

把(s[r] - s[l-1]) % k == 0 中的l-1换为l,则由于l-1的范围在0~ r-1,则l的范围在1~r,
原式变为(s[r] - s[l]) % k == 0 再由数学知识变为 s[r] % k == s[l] % k,所以只需找到前面的取余结果与s[r]取余结果相同的数的个数即可。

cnt[i]表示为存放 某个数取余k余数为i的数的个数

maxk += cnt[s[i]%k]; 先累加 某个数%k 与 s[i]%k相等的值

再由cnt[s[i]%k]++; 更新(加入当前循环的结果)取余为 s[i]%k 的值的个数

cnt[0] = 0;是因为在进入i从1开始的循环时,余数为0的数已经有了一个了,即为s[0]。