蓝桥杯真题里有一类题刚看第一眼你会觉得它是纯枚举看完数据范围后又会觉得它怎么可能是枚举。k倍区间就是这个套路。当年我第一次在真题集里碰到它顺手写了个二重循环样例倒是能过提交上去只拿了个部分分。后来认真啃下“前缀和 余数统计”这个组合拳才明白这道题其实是在考你对“前缀和取模”这个工具的敏感度。简单说这道题要你统计一个长度为 N 的数列里有多少个连续子区间的和正好是 K 的倍数。N 和 K 都在 10^5 级别暴力枚举区间是 O(n^2)必死。真正能 AC 的做法只需要 O(n) 复杂度核心就两句话用前缀和把区间和变成两个前缀和之差差是 K 的倍数等价于两个前缀和对 K 取模的余数相等。这篇文章我把完整推导、三种主流语言的写法、考场上的坑和几类变式一次讲透适合正在备战蓝桥杯、或者刚学前缀和想找经典题加深理解的选手。1. 先搞懂题目在问什么k倍区间的本质1.1 题面与数据范围题目原文大致是这样给定长度为 N 的数列 A1, A2, ..., AN如果其中一段连续子序列 Ai, Ai1, ..., Aj 之和是 K 的倍数就称区间 [i, j] 是 K 倍区间。要求统计总共有多少个 K 倍区间。输入输出格式很简单第一行给 N 和 K第二行给 N 个整数。关键在数据范围N 和 K 都到 10^5 级别每个 Ai 也是正整数。这个范围直接判了暴力死刑——如果 N 是 100000理论上有大约 N*(N1)/2 个区间要枚举也就是 50 亿个区间哪怕一个区间只算一次加法在竞赛时限内也完全不可能跑完。所以一看到“合法区间数量”这个统计量第一反应就应该是肯定有什么办法能一次性算出大量区间的性质而不是把每个区间都遍历一遍。前缀和就是为“快速得到一个区间和”而生的工具。1.2 暴力做法为什么过不了我先把暴力思路写出来不是为了让大家用而是为了对比后面优化的收益。两层循环枚举左端点 l 和右端点 r每次计算 s[r] - s[l-1] 是否整除 Kint ans 0; for (int l 1; l n; l) { for (int r l; r n; r) { // 区间 [l, r] 的和 int sum 0; for (int i l; i r; i) sum a[i]; if (sum % k 0) ans; } }如果内层再用一重循环累加那就是 O(n^3)N1000 都费劲。先用前缀和优化成 O(n^2)即每对 (l, r) 通过前缀和 O(1) 求得区间和N10^5 时依然是天文数字。暴力代码不是没用它的价值在于“验证样例”和“确认题意”。我刷题的习惯是拿到任何一道题先写一个绝对正确但可能很慢的版本把样例跑通再去想优化。这样至少确保自己没有理解错题。k倍区间这道题一旦你写出了二重循环的版本下一步自然就会琢磨能不能把“枚举左端点”这层循环干掉答案是能而且方法非常优雅。2. 核心优化思路前缀和与余数同余2.1 区间和与两个前缀和之差设前缀和数组 S其中 S[i] 表示数列前 i 个元素的和特别地 S[0] 0。那么任意区间 [l, r] 的和都可以写成sum(l, r) S[r] - S[l-1]这个公式是前缀和的灵魂。S[r] 是前 r 个元素的总和S[l-1] 是前 l-1 个元素的总和两者相减自然就是第 l 个到第 r 个元素的和。注意这里的下标从 1 开始所以 S[0] 这个空前缀非常关键。题目要求的是 sum(l, r) 能被 K 整除也就是(S[r] - S[l-1]) % K 0到这里还只是普通的前缀和优化。真正的神来之笔在于判断“两个数的差是 K 的倍数”和判断“两个数对 K 取模的余数相等”是完全等价的。2.2 从“差是 k 的倍数”到“余数相等”为什么如果 a % K b % K假设余数都是 r那么 a xK rb yK r所以 a - b (x-y)*K差一定是 K 的倍数。反过来如果 a - b 是 K 的倍数那么 a 和 b 除以 K 的余数必然相同。这个等价关系一旦用上上面的条件就变成了S[r] % K S[l-1] % K于是问题就从“找区间 [l, r]”变成了“找两对余数相等的 S 值”。S 数组有 N1 个值只要统计相同余数出现了多少次然后两两配对就能算出答案。我举个例子帮助理解。假设数组是 [1, 2, 3, 4, 5]K 2。前缀和 S 为S[0] 0S[1] 1S[2] 3S[3] 6S[4] 10S[5] 15对 2 取模后余数序列是011001余数为 0 的前缀有 S[0]、S[3]、S[4]任意两个配对得到的区间分别是 [1,3]、[1,4]、[4,4]和分别为 6、10、4全是偶数。余数为 1 的前缀有 S[1]、S[2]、S[5]配对得到 [2,2]、[2,5]、[3,5]和分别为 2、14、12也全是偶数。所以这个数列的 K 倍区间总数就是 C(3,2) C(3,2) 6 个。从枚举区间变成统计配对这就是 k倍区间这道题最核心的思想跃迁。2.3 余数统计如何省掉一重循环有了上面的结论实现上不需要真的先把所有前缀和的余数算出来再排序统计那样不是最优。更简单的做法是边读入边计算前缀和每得到一个前缀和余数就看看之前这个余数已经出现过多少次。每出现一次“之前也遇到过同余前缀”就说明当前这个位置能和之前那个位置之间构成一个新的 K 倍区间。注意一个细节当前前缀和本身是余数 r而我们需要的是“左端点前面的那个 S[l-1] 的余数也是 r”。对于当前遍历到的右端点 r它可以和所有之前的左边界形成新区间所以把答案累加“之前相同余数的出现次数”然后把自己这次的余数也加进计数里顺序不能反。我把这个流程模拟一下。还是上面的例子从头开始预处理cnt[0] 1代表空前缀 S[0]。读到 1S 1余数 1。cnt[1] 当前是 0ans 0然后 cnt[1] 1。读到 2S 3余数 1。cnt[1] 当前是 1ans 1说明以当前位置为右端点有一个新区间 [2,2] 满足条件。然后 cnt[1] 2。读到 3S 6余数 0。cnt[0] 当前是 1ans 1对应区间 [1,3]。然后 cnt[0] 2。读到 4S 10余数 0。cnt[0] 当前是 2ans 2对应区间 [1,4] 和 [4,4]。然后 cnt[0] 3。读到 5S 15余数 1。cnt[1] 当前是 2ans 2对应区间 [2,5] 和 [3,5]。最终 ans 0 1 1 2 2 6和前面组合数算的一样。整个扫描过程只有一层循环时间复杂度 O(n)空间复杂度 O(K)。3. 代码实现三种主流语言的写法与微调3.1 C版本用数组统计余数最快最稳蓝桥杯的 C 组选手用这个版本最舒服。因为 K 的范围只有 10^5余数最多 K 种开一个长度为 K 的 long long 数组即可比哈希表快很多也不会因为哈希冲突出岔子。#include bits/stdc.h using namespace std; const int MAXK 100005; long long cnt[MAXK]; int main() { int n, k; cin n k; long long ans 0; int sum 0; cnt[0] 1; for (int i 0; i n; i) { int x; cin x; sum (sum x) % k; ans cnt[sum]; cnt[sum]; } cout ans endl; return 0; }注意几个细节cnt 数组要用 long long。虽然单个余数的出现次数最多也只是 N1不会超过 int但答案累加过程中涉及乘法级别的增长保险起见都用 long long。sum 每次取模后始终保持 [0, K-1] 之间由于题目里 Ai 是正整数sum 不会为负直接(sum x) % k就够了。cnt[0] 1 是必需的初始化否则当某个前缀和本身是 K 的倍数时会漏掉“整个左边界从第 1 个元素开始”的那些区间。3.2 Java版本HashMap计数的注意点Java 里没有 C 那种“余数范围确定”时可以直接开数组的爽快感但用 HashMap 也完全能过。关键在于 getOrDefault 的用法能省不少事。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); MapInteger, Long cnt new HashMap(); cnt.put(0, 1L); long ans 0; int sum 0; for (int i 0; i n; i) { int x sc.nextInt(); sum (sum x) % k; ans cnt.getOrDefault(sum, 0L); cnt.put(sum, cnt.getOrDefault(sum, 0L) 1); } System.out.println(ans); sc.close(); } }如果你希望更快一点也可以根据 K 的大小判断当 K 不超过 10^6 时用 long[] 数组代替 HashMap 会快很多。蓝桥杯的 Java 组通常时间比较紧张能省一点是一点。3.3 Python版本灵活但要注意性能Python 写这个题核心逻辑非常简洁直接用 dict 统计余数即可。注意 Python 的%运算结果一定非负所以不需要像 C 那样担心负数取模的问题。def solve(): n, k map(int, input().split()) a list(map(int, input().split())) cnt {0: 1} ans 0 s 0 for x in a: s (s x) % k ans cnt.get(s, 0) cnt[s] cnt.get(s, 0) 1 print(ans) if __name__ __main__: solve()Python 版本在 N10^5 时完全没问题但如果你怕蓝桥杯的测试环境 Python 比较慢可以试试把cnt.get的次数减少一点比如先cur cnt.get(s, 0)再ans cur、cnt[s] cur 1能省一点点时间。4. 踩坑实录考场和调试中容易翻车的细节4.1 int溢出与long long的必要性这是我最想强调的坑之一。N 最大 10^5每个 Ai 最大 10^5那么前缀和 S 的最大值在 10^10 数量级int 能表示的最大值才 21 亿左右直接用 int 存前缀和早就溢出了。答案的最大情况是 N*(N1)/2N100000 时约 5*10^9同样超出 int。所以代码里 sum 参与累加的地方我用的是 int 还是 long long 要看具体写法但 ans 一定是 long long。C 里如果不小心int ans样例小数据没事大数据直接错得离谱。有个小技巧不确定会不会溢出的时候干脆所有跟“累加总和”“答案计数”相关的变量一律 long long让编译器帮你去兜底代价只是多占几个字节完全不亏。4.2 边界与初始化为什么 cnt[0] 1很多初学者卡在这。cnt 统计的是“前缀和余数出现的次数”而区间左边界对应的前缀是 S[l-1]l-1 可以等于 0也就是说可能存在一个区间从第 1 个元素开始它的左边界“前面的前缀”就是 S[0] 0。所以 S[0] 也要作为一个合法的前缀计入统计。如果不初始化 cnt[0] 1那么当 S[r] 的余数恰好是 0 时你就漏掉了形如 [1, r] 的那些区间。比如数列是 [2, 4, 6]K 2S[3] 12余数 0此时只有把空前缀算进去才能统计到整个 [1,3] 这个区间。4.3 取模结果出现负数怎么办原题 Ai 是正整数直接用(sum x) % k没问题。但如果你以后在别的题里遇到负数或者想把代码写得更健壮C 的%在 C11 之后是“向零取整”-1 % 5 的结果是 -1 而不是 4直接拿它当下标会越界。标准写法是sum ((sum x) % k k) % k;这样无论 sum x 是正是负最终都会落在 [0, k-1] 区间。这个习惯养成之后遇到需要取模的题都能少踩很多坑。4.4 数组统计与哈希表的取舍我在 C 版本里选择了定长数组因为 K ≤ 10^5这个前提让数组方案非常简单高效。但如果题目改成 K 很大比如 K 达到 10^9数组开不下那就得用 unordered_map 或者 map。选型的逻辑很清楚余数范围小且知道上界 → 定长数组O(1) 访问常数极小。余数范围大、上界未知 → 哈希表O(1) 平均访问但常数大。有余数顺序需求比如求最小索引 → map 或 按序处理。一般竞赛题能开数组就优先开数组哈希表只在不得已时使用。5. 另一条路排序后按余数分组统计5.1 思路与实现除了边扫边统计的在线做法还有一种离线做法同样经典把所有前缀和的余数都算出来排个序把相同余数分成一组。每组里有 m 个元素那么这一组能产生的 K 倍区间个数就是 C(m, 2) m*(m-1)/2最后求和。核心代码如下vectorint mods; mods.push_back(0); int sum 0; for (int i 0; i n; i) { int x; cin x; sum (sum x) % k; mods.push_back(sum); } sort(mods.begin(), mods.end()); long long ans 0; for (int i 0; i (int)mods.size(); ) { int j i; while (j (int)mods.size() mods[j] mods[i]) j; long long m j - i; ans m * (m - 1) / 2; i j; }这个做法时间复杂度 O(n log n)主要花在排序上。它在统计思路上更加直观既然同余前缀两两配对那我干脆数出一共有几个同余前缀再算组合数。它不依赖哈希表也不用考虑 cnt[0] 的初始化顺序适合理解原理之后当第二种写法练手。5.2 两种解法的适用场景对比两种方法各有适用场景解法时间复杂度空间复杂度优点缺点边扫边统计O(n)O(K)快适合大范围数据要理解“先查后更新”的顺序排序分组统计O(n log n)O(n)思路清楚适合辅助理解多一次排序常数略大如果你是为了竞赛拿分首选第一种。如果你是为了讲给别人听、加深理解第二种反而更容易画图说明白。我当年就是把两种都写了一遍才彻底搞懂这道题为什么能这么优化。6. 题目变式与场景迁移6.1 动态修改的前缀和问题原题是静态数组一次查询统计所有 K 倍区间。但如果数组支持单点修改那每次查询都会重新影响大量前缀和静态的一次扫描方案就不够用了。这时候一般要借助树状数组或线段树维护前缀和查询和修改各 O(log n)整体复杂度会是 O(n log n) 起步。有些进阶题会这样考给你一个初始数组然后有一堆“单点修改 询问当前数组中 K 倍区间个数”的操作。这类题不能每次修改后都整体重扫而是要在每次修改时分析这个变化影响了哪些前缀和再增量更新答案。树状数组在这里的作用是快速定位某个区间内的前缀和信息。不过蓝桥杯省赛考察这个程度的概率不高主要出现在校赛或国赛的压轴场景。我会建议先把静态版本彻底吃透再去看动态版本否则很容易被复杂度绕晕。6.2 更多变式最长区间和二维矩阵同样是“前缀和 余数统计”这个组合可以延伸出不少变式求最长的 K 倍区间不再统计个数而是在扫描时记录每个余数首次出现的位置。当前余数 r 如果之前出现过就用当前位置减去最早出现位置更新最大长度。这时 map 或数组存的就是“最早位置”而不是“出现次数”。二维 K 倍子矩阵把矩阵每行做前缀和然后枚举上下边界把上下边界之间的每一列累加成一个一维数组问题就变回一维的 K 倍区间。复杂度 O(n^2 * m)如果矩阵维度在几百级别完全可接受。区间和恰好等于某个特定值的个数如果不取模而是直接用原始前缀和值做统计也可以用类似思路y 用 map 记录原值出现次数每扫到一个前缀和 S[r]就查 S[r] - target 的个数。这些变式本质都在做一件事把“区间条件”转换成“前缀和在某种映射下的相等关系”。一旦理解了这一点遇到任何区间统计题你的第一反应就会是前缀和。6.3 蓝桥杯考场上的得分策略实战中蓝桥杯是“按测试点给分”的比赛不一定要求你满分。如果考场上暂时想不出最优解我会这样分配时间先写能过小数据的暴力至少拿下前 20% 到 40% 的分数。再根据数据范围猜复杂度看到 N10^5基本确定标准做法是 O(n log n) 或 O(n)这时候往前缀和、二分、双指针这些方向靠。如果时间还剩再写优化版本替换暴力。k倍区间这道题还有一点非常友好代码极短核心逻辑也就十几行。只要你理解了余数统计考场上是可以快速写出来的完全不用怕代码量。我在实战中的一点体会刷了这么多蓝桥杯真题越来越觉得这类题的难点不在代码而在于“敢不敢把枚举区间转化为统计前缀”。k倍区间最妙的地方在于它让你亲眼看到一次数学等价变换如何把 O(n^2) 砍到 O(n)。我建议大家拿到这道题后先别看题解自己用笔在纸上推导一遍前缀和取模的配对关系再上手写代码这样印象会深很多。如果你已经能独立 AC 这题下一步可以去试试同类型的“和为 K 的子数组”、“连续子数组的最大异或值区间”这类题它们的核心思想和 k倍区间同源都是前缀和配合某种统计结构。我个人练下来的感觉是一旦吃透了“前缀和 相等条件”这套模板蓝桥杯里至少三分之一的数据结构题能秒出思路。