分析

• 任取两个相同的红色数字【前缀和对k取模】，一定能得到一个合法的k倍区间。用cnti记录i的个数，问题转化为对每个cnti考察从中选两个，所有加起来一共有多少种选法。

• 最后加上单个合法区间cnt0的个数，就是正确答案。

• 最后解释一下 怎么来一定找到k倍区间 ？考虑上方第一个1下标为i(=1),最后一个1下标为j(=5)，那么这一对必然能使得 区间[i+1,j]为k倍区间，它的和为s[j]-s[i]=(t0*k+1)-(t1*k+1)=m*k可以发现相同的余数被抵消了<-.->

c++

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)
#define readll(x) scanf("%lld",&x)
#define readi(x) scanf("%d",&x)
#define out(x) cout<<x<<" "
#define nl cout<<endl
#define outa(a) ffor(i,0,n) out(a[i]); nl
typedef long long LL;
const int N=100010;

//data
int a[N];
int sum[N];
int cnt[N];
int n,k;


//fun
void init(){
    readi(n);
    readi(k);

    ffor(i,0,n){
        readi(a[i]);
        if(!i) sum[i]=a[i]%k;
        else{
            sum[i]=(sum[i-1]+a[i])%k;
        }
    }

    //outa(a);
}

LL Cn2(int x){
    int nxt=x-1;
    (x&1) ? nxt>>=1 : x>>=1;
    return (LL)x*nxt;
}

void getAns(){
    LL ans=0;
    ffor(i,0,k){
        if(cnt[i]){
            ans+=Cn2(cnt[i]);
        }
    }
    cout<<ans+cnt[0]<<endl;
}


//Ac flow
void Ac(){
    init();
    ffor(i,0,n) cnt[sum[i]]++;
    getAns();
}

int main(){
    //init();

    Ac();
    return 0;
}