模k余数相同的前缀和即为一个合法区间
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6;
int n, k;
int s[N];
int st[N];
int main()
{
cin >> n >> k;
ll ans = 0;
st[0] = 1;
for(int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
s[i] = (s[i - 1] + x) % k;
ans += st[s[i]];
st[s[i]] ++ ;
}
cout << ans;
}