题解
题意简述
给定 \(n\) 个数，求这 \(n\) 个数中有多少个二元组 \((x,y)\) 满足其中每一个数都是 \(m\) 的倍数。
思路
前缀和，\((x,y)\) 内每一个数 \(\bmod \ m = 0\)，可以用 \((sum_y - sum_{x - 1}) \bmod \ m = 0\) 表示。但是这题数据太大，所以要使用 map。
如果 \(x = 1\)，那么 \(sum_{x - 1} = sum_0\)，所以要先给 \(sum_0\) 赋值为 \(1\)
AC Code
#include<bits/stdc++.h>
using namespace std;
int n, m, x;
map<long long, int> cnt;
long long sum, ans;
int main(){
cin >> n >> m;
cnt[0] = 1;
for (int i = 1; i <= n; i++){
cin >> x;
sum += x;
ans += cnt[sum % m];
cnt[sum % m]++;
}
cout << ans;
return 0;
}