k倍区间（同余定理与组合计数）
问题描述
给定一个长度为 N 的序列 a₁, a₂, ..., a_N，寻找所有满足以下条件的连续子序列：若子序列 aᵢ, aᵢ₊₁, ..., aⱼ（i ≤ j）之和能够被 K 整除，则称区间 [i, j] 为 K 倍区间。
请统计满足条件的 K 倍区间总数。
输入格式
第一行包含两个整数 N 和 K（1 ≤ N, K ≤ 10⁵）。
接下来 N 行，每行包含一个整数 aᵢ（1 ≤ aᵢ ≤ 10⁵）。
输出格式
输出一个整数，表示 K 倍区间的数量。
样例输入输出
输入样例：
5 2
1
2
3
4
5
输出样例：
6
解题思路
最直观的想法是使用前缀和枚举所有区间，时间复杂度为 O(N²)，对于 N = 10⁵ 的数据规模显然会超时。
优化思路基于数论中的同余定理：当两个数除以 K 的余数相同时，这两个数之差一定能被 K 整除。
设前缀和数组为 prefix，其中 prefix[i] 表示 a₁ + a₂ + ... + aᵢ。若要计算区间 [l, r] 的和，等价于 prefix[r] - prefix[l-1]。要使该区间和能被 K 整除，需要满足 prefix[r] % K == prefix[l-1] % K。
因此，我们只需统计每个前缀和除以 K 的余数出现的次数。当两个位置的余数相同时，它们之间的区间就是 K 倍区间。
利用组合数学公式，对于每种余数 r，假设其出现了 cnt[r] 次，则能够形成的 K 倍区间数量为 C(cnt[r], 2) = cnt[r] × (cnt[r] - 1) / 2。
特别需要注意 prefix[0] = 0 的情况，它代表空前缀，也需要计入余数为 0 的统计中。
解法一：组合数计数
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long cnt[MAXN]; // 存储各余数出现的次数
long long n, k;
long long answer = 0;
long long currentMod = 0;
int main() {
cin >> n >> k;
// 读取数组并计算前缀和的余数
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
currentMod = (currentMod + x) % k;
cnt[currentMod]++; // 桶计数方式记录余数
}
cnt[0]++; // 将 prefix[0] = 0 计入（空区间的情况）
// 遍历所有可能的余数，计算组合数并累加答案
for (int i = 0; i < k; i++) {
answer += cnt[i] * (cnt[i] - 1) / 2;
}
cout << answer;
return 0;
}
该算法的时间复杂度为 O(N + K)，空间复杂度为 O(K)。
解法二：逐次累加统计
另一种实现方式是边遍历边统计。对于每个位置的前缀和余数，我们累加之前出现过相同余数的次数，这是因为每出现一次相同余数，就对应着一个新的 K 倍区间。
同时，如果当前前缀和余数为 0，说明从起始位置到当前位置的区间本身就是一个 K 倍区间。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long prefix[MAXN]; // 前缀和数组
long long freq[MAXN]; // 各余数出现频次
long long n, k;
long long result = 0;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
prefix[i] = (prefix[i-1] + x) % k;
// 先累加之前出现的相同余数次数，再更新频次
result += freq[prefix[i]];
freq[prefix[i]]++;
}
// 余数为0的情况包括 prefix[0]=0 本身形成的区间
cout << result + freq[0];
return 0;
}
这里需要注意的是，必须先使用 freq 计数再加 1，以确保当前元素不被计入本次统计。两种解法本质上相同，只是实现角度不同。
