一个比较容易理解的解法
sum, ans分别用来 求和、记录答案

1. 先求出前缀和，并用hash记录每个前缀和出现的次数 （这里是求k的倍数，所以记录每个前缀和%k后出现的次数）

2. 从前往后求一遍数组的和，sum每加上一个a[i]，就让对应$hash[sum\%k]-\-$ , $ans+hash[sum\%k]$;

第2步相当于，对于后面出现的所有等于sum%k的前缀和，除去一个sum%k，那么它的和%k一定是0，它的数量就是k倍区间的一部分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 1e5+5;
typedef long long LL;
int a[N];
int main(){
    unordered_map<int, int>mp;
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++) cin>>a[i];

    LL sum=0;
    for(int i=1; i<=n; i++){
        sum+=a[i];
        mp[sum%k]++;
    }

    LL ans=mp[0];
    sum=0;
    for(int i=1; i<=n; i++){
        sum+=a[i];
        mp[sum%k]--;
        ans+=mp[sum%k];
    }

    cout<<ans<<endl;
    return 0;
}

参考文献

CSDN issue是fw