1230. K倍区间

原题链接

思路

前缀和应用

正常想法O（n^2）

求前缀和后根据端点遍历另一个端点。

想到求余数（性质）可优化到O（n）

前缀和是a1~ai的和，那么a？ ~ ai的和的余数为0只要a1~a？的余数等于a？ ~ai的余数即可。

所以用一个新数组存前缀和余数，然后直接根据判断满足的个数即可。

相当于优化掉了根据端点遍历另一个端点的时间。

注意

LL问题（a[i]要用LL，我这里%k了可以不用）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int a[N], c[N];

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        a[i] = (a[i] + a[i - 1]) % k;
    }
    long long res = 0;
    c[0] ++;
    for(int i = 1; i <= n; i ++)//右端点 
    {
        res += c[a[i] % k];
        c[a[i] % k] ++;
    }
    cout<< res;
}