令\(s[i]\)表示\(s[i]=(a_1+a_2+...+a_i) mod k\)，则以\(r\)为区间右端点的区间数量为\([1,r-1]\)中余数与\(s[r]\)相同的元素数量。特别的，\(s[r]=0\)时，额外加1。

#include<cstdio>
using namespace std;

const int MAXN = 1e6+10;
const int MAXK = 1e6+10;

int a[MAXN],s[MAXN];
int mod[MAXK];

int main() {
    int n,k;long long ans=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) {
        scanf("%d",a+i);
        s[i]=(s[i-1]+a[i])%k;
        ans+=mod[s[i]];
        if(s[i]==0) ans++;
        mod[s[i]]++;
    }
    printf("%lld",ans);
    return 0;
}