可通过的代码 找相同余数的前缀和来计算能有多少个区间

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;//注意1 
const int N = 1e5 + 10;
int n,k;
LL pre[N];
LL rest[N];//存余数

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ){
        cin >> pre[i];
        pre[i] += pre[i-1];
    }
    LL ans = 0;
    rest[0] = 1;//注意2 下面循环没有包含i=1 但是其实pre[0]%k = 0应该计入
    for(int i = 1;i <= n;i++){
        ans += rest[pre[i]%k];
        rest[pre[i]%k] ++;
    }
    cout << ans;    
    return 0;
}

普通的前缀和 会超时

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n,k;
int a[N];
int pre[N];
int rest[N];//存余数

int main(){

    cin >> n >> k;
    for (int i = 1; i <= n; i ++ )cin >> a[i];
    for (int i = 1; i <= n; i ++ ){
        pre[i] = a[i] + pre[i-1];//前缀和
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        ans += rest[pre[i]%k];
        rest[pre[i]%k] ++;
    }
    cout << ans;    
    return 0;
}