每日一题洛谷P8649 [蓝桥杯 2017 省 B] k 倍区间c++

P8649 [蓝桥杯 2017 省 B] k 倍区间 - 洛谷 (luogu.com.cn)

#include <iostream>
#include <vector>
using namespace std;
#define int long long
signed main() {int n, k;cin >> n >> k;vector<int> a(n + 1);vector<int> sum(n + 1);vector<int> cnt(k);sum[0] = 0;cnt[0] = 1;for (int i = 1; i <= n; i++) {cin >> a[i];sum[i] = (sum[i - 1] + a[i]) % k;cnt[sum[i]]++;}int count = 0;for (int i = 0; i < k; i++) {count += cnt[i] * (cnt[i] - 1) / 2;}cout << count << endl;return 0;
}