题意

给一个数组，求有多少区间的和是$k$的倍数

算法

枚举 $O(n^3)$

可以很简单的写出暴力代码，直接三重循环

for(int r = 1; r <= n; r ++)
    for(int l = 1; l <= r; l ++)
    {
        int sum = 0;
        for(int i = l; i <= r; i ++)
            sum += a[i];
        if(sum % k == 0) ans ++;
    }

枚举左右区间端点l,r，求出区间和sum判断是否为k的倍数，然后记录在答案ans上。
可以看出第三重循环的作用就是算出区间[l,r]的和，所以用前缀和来优化这重循环。

前缀和 $O(n^2)$

预处理一下数组a[]，将前缀和存入s[]中，每次查询就只需要$O(1)$的时间了

for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i]; // 求前缀和

for(int r = 1; r <= n; r ++)
    for(int l = 1; l <= r; l ++)
        if((s[r] - s[l - 1]) % k == 0) ans ++;

但是这个时间还是会炸，所以还需要优化一层。

数学 $O(n)$

第二层循环的作用是枚举左端点，写出来就是(s[r] - s[0, r - 1]) % k = 0,当这个条件成立答案就加一。

化简:

$$ s[r] \% k \equiv s[0, r - 1] \% k $$

现在这个式子的意思就是：在模k的情况下，之前所有点和当前点有都少个相等。
所以再开一个额外的数组cnt[]记录每个前缀和取余k的余数的数量，遍历一遍就行了。

代码 $O(n)$

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

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

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i ++)
        scanf("%d", s + i), s[i] += s[i - 1];   //求前缀和

    LL ans = 0;
    cnt[0] = 1; //初始化
    for(int i = 1; i <= n; i ++)
    {
        ans += cnt[s[i] % k];   
        cnt[s[i] % k] ++;   // 前缀和取余k的余数的数量
    }
    cout << ans << endl;
}

这里要注意初始化cnt[0] = 1，因为上一步中l的取值范围是[0, r - 1]。

总结这类题目：
https://www.acwing.com/blog/content/56820/