如果寻找 (a[r] - a[l-1]) % k == 0
有性质 a[r] % k == a[l-1] % k
即如果a[r] % k 和 a[l-1] % k 的模相等,必然相减也相等
那么我们就只需要预处理出所有的对k的余数,然后找相等的就可以了
最后因为有可能只需要 a[r] 就使得是 k倍区间,所以我们加上这种特例
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
LL a[N];
unordered_map<LL,int> h;
int n , k;
int main(){
cin >> n >> k;
LL res = 0;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i-1];
if(a[i] % k == 0) res ++;
res += h[a[i] % k] ++;
}
cout << res;
}