【前缀和】蓝桥杯-K倍区间

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？

输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含一个整数 Ai。

输出格式
输出一个整数，代表 K 倍区间的数目。

数据范围
1≤N,K≤100000,
1≤Ai≤100000

输入样例：

5 2
1
2
3
4
5

输出样例：

6

首先，暴力枚举，先确定一个右端点，然后确定一个左端点，然后在对区间求和，看是不是k的倍数，这样一个O(n^3^)的复杂度，是一个三重循环的嵌套；

1、简化，首先把最里面的求和的循环修改成前缀和数组的查找，这样就成了一个O(1)的复杂度了；

2、我们要求的就成了，对每一个R，在1-R上有多少个L能满足（S[R] - S[L - 1]）% k == 0;

3、进行一下转化，把等式中L- 1换成L，那么区间就变成了0 -- R-1

4、也就是说，对每一个确定的R，有多少个S[L] % k == S[R] % k;

那么我们定义一个数组，第i个位置表示余数是i的有几个。这样我们只需要进行一次遍历，每次算一下这个的余数，然后直接看数组里面余数是i的有几个（这看的就是对于固定的R的所有的L了，因为R是遍历过去的，每次遍历都会进行计算并且更新这个数组）代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;

int n, k;
LL s[N], cnt[N];

int main()
{
    scanf("%d%d", &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 i = 1; i <= n; i ++ )
    {
        res += cnt[s[i] % k];
        cnt[s[i] % k] ++;
    }

    cout << res << endl;

    return 0;
}