蓝桥杯里有一道题我在备赛群里看到它的频率高得惊人人称“k倍区间”。很多人第一次做它的时候卡住的点非常一致明明读懂了题暴力也能写一提交就是超时看了别人代码又觉得“就这我也想到前缀和了怎么就没写出来”。这道题在蓝桥杯真题里反复出现考的是两个基础但极其重要的算法思维——前缀和与余数统计。你如果把它彻底吃透后面遇到“连续子数组和满足某种条件”的题目基本都能秒联想到解法。这篇文章我就按自己的刷题过程把从暴力到正解的完整推导、代码细节、和踩坑经验拆开讲清楚不管你用C还是Python应该都能直接抄作业。1. 先看清题目k倍区间到底在问什么1.1 题目描述与数据范围题目一般长这样给定一个长度为N的数列a[1..N]要求计算有多少个区间[l, r]1 ≤ l ≤ r ≤ N使得区间内所有数的和是K的倍数。注意几个关键词区间连续和不是积也不是差K的倍数也就是能被K整除余数为0。数据范围很关键。蓝桥杯这种题N通常给到10^5甚至10^6K的取值范围一般是1到10^5。这个范围就是明晃晃的提示别想用O(N^2)暴力过老老实实往O(N)或者O(N log N)的方向去想。我拿一个具体例子来跑完整过程后文一直用它验证N 5, K 2 a [1, 2, 3, 4, 5]先人工数一下答案。所有区间有15个一个个算和太费劲我们稍微分组长度为1[1]1不满足[2]2满足[3]3不满足[4]4满足[5]5不满足共2个长度为2[1,2]3不满足[2,3]5不满足[3,4]7不满足[4,5]9不满足共0个长度为3[1,3]6满足[2,4]9不满足[3,5]12满足共2个长度为4[1,4]10满足[2,5]14满足共2个长度为5[1,5]15不满足共0个加起来是6个。这个结果先放这后面所有解法都拿它验证。1.2 暴力枚举为什么必死很多人第一反应就是三层循环枚举左端点l枚举右端点r然后循环求和判断。这确实最直观但复杂度是O(N^3)N10^5时根本不可能跑完。就算有人想到先做前缀和把区间和变成O(1)查询剩下还是要枚举所有区间复杂度O(N^2)。N10^5时区间数量是N(N1)/2约5×10^9个C每秒大概能跑10^8到10^9次简单操作这得几十上百秒Python更惨每秒10^7次左右要跑十几分钟。这还没算取模和累加的开销实际更慢。所以这道题表面问的是“有多少个区间”真正的考验是你能否不枚举区间换个角度把它数出来。这就是奥林匹克里常说的“计数问题”思维——不是把答案一个个找出来而是通过数学规律直接算出数量。2. 前缀和把区间和变成两个数的差2.1 前缀和的定义与构建前缀和这个概念现在网上资料很多但我还是用自己的话重新说一遍因为后续所有推导都建立在这上面。定义一个数组s长度为N1s[0] 0 s[i] a[1] a[2] ... a[i]也就是说s[i]表示原数组前i个数的总和。构建方式特别简单s[i] s[i-1] a[i]比如我们的例子a [1, 2, 3, 4, 5] s [0, 1, 3, 6, 10, 15]有了s任意区间[l, r]的和就不用从头加到尾了直接一个减法sum(l, r) s[r] - s[l-1]注意是s[l-1]不是s[l]因为s[l]里已经包含了a[l]减掉就错了。初学者这里特别容易犯迷糊。用例子验证区间[2, 4]即a[2]a[3]a[4] 234 9。用前缀和算s[4] - s[1] 10 - 1 9正确。2.2 从“枚举区间”到“枚举边界”的思维转变前缀和这一步看似只是优化了求和但它带来一个更重要的思维转变区间[l, r]现在变成了两个前缀和s[r]和s[l-1]之间的关系。原来的视角是“区间是一个整体”现在的视角变成“区间由两个边界点唯一确定”。这两个边界点本质上就是前缀和数组里的两个下标i l-1j r满足0 ≤ i j ≤ N。所以问题变成了在s[0]到s[N]这N1个数里有多少对(i, j)满足s[j] - s[i]是K的倍数为什么说这个转变重要因为枚举区间需要两层循环而枚举“前缀和之间的配对关系”可以走另一条路——我们不关心具体是哪些配了对只关心配对数量。这个数量能不能通过某种统计直接算出来能这正是下一步的核心。3. 余数统计同余与配对的灵魂一步3.1 数学推导倍数判断转化为同余判断现在的问题核心是有多少对前缀和之差能被K整除。这里用到数论里最基础的同余概念。两个数a和b如果(a - b)能被K整除我们就说a和b模K同余记作a ≡ b (mod K)。等价的说法就是a % K b % K。这个性质用生活类比特别好懂想象一个只有K个刻度的表盘走完一圈回到同一个位置。两个时刻落在同一个刻度上说明它们相差的时间一定是K的倍数。K倍区间的问题本质上就是在问这些前缀和都落在哪个刻度上落在同一个刻度上的有哪些。于是判断条件s[j] - s[i]是K的倍数等价于s[j] % K s[i] % K。这就把问题彻底改写成了给定N1个前缀和s[0..N]问有多少对前缀和它们对K取余的结果相同。这个改写厉害在哪里它把“差值整除”这种涉及两个数之间关系的问题变成“分别看每个数的余数再归类统计”的问题。关系问题原来要两两比较现在只需要每个数单独求一次余数然后按余数分组。3.2 分组配对与cnt[0]1的由来接下来就很简单了把前缀和按余数分组假设余数为r的前缀和一共有c个那么这一组内部可以配出C(c, 2) c(c-1)/2对。把每个余数组的配对数加起来就是答案。还是用例子算一遍。a [1,2,3,4,5]K2前缀和s [0, 1, 3, 6, 10, 15]每个对2取余s: 0, 1, 3, 6, 10, 15 余数: 0, 1, 1, 0, 0, 1余数0出现了3次s[0]、s[3]、s[4]贡献C(3,2)3对余数1出现了3次s[1]、s[2]、s[5]贡献C(3,2)3对。总计6对和之前手算的答案一致。注意这里s[0] 0是我们虚拟出来的前缀和它代表空区间。如果不把它算进余数0的组里那所有左端点l1的区间——也就是从a[1]开始的那些——就全被漏掉了。比如例子里余数0的配对一共3个s[0]和s[3]配对对应区间[1,3]s[0]和s[4]配对对应区间[1,4]s[3]和s[4]配对对应区间[4,4]。如果没有s[0]前两个就没了。这就是后面所有代码里第一行cnt[0] 1的原因。3.3 一次扫描累加的实现思路理解了分组配对代码还有两种写法。第一种是先把所有前缀和的余数统计完再用组合数公式统一计算。第二种更巧边读数据边统计边累加只需一遍扫描空间O(K)。我推荐第二种因为它在竞赛里最常用而且代码极短。核心逻辑是每读入一个数x更新当前前缀和pre (pre x) % K 此时pre的余数是r 前面所有余数也为r的前缀和cnt[r]个每一个都可以和当前这个前缀和配成一对合法区间 所以 ans cnt[r] 最后 cnt[r]把当前前缀和计入统计为什么边扫描边累加能得到和组合数公式一样的结果可以这样理解假设某个余数r最终一共出现了c次。在扫描过程中第二个同余前缀和出现时累加1第三个出现时累加2第c个出现时累加c-1正好加起来是12...(c-1) c(c-1)/2就是组合数。所以两种写法等价只是第一种先算完再统一算组合数第二种边扫描边把配对关系数出来。这里还有一个极其重要的细节必须先ans cnt[pre]再cnt[pre]。如果顺序反了先自增再累加就会把自己和自己配成一对相当于多算了一个“长度为0的区间”结果必然偏大。这个坑我见过很多人踩。4. 完整代码与关键细节4.1 Python版本蓝桥杯Python组可直接用import sys def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) k int(data[1]) a list(map(int, data[2:2 n])) cnt [0] * k cnt[0] 1 ans 0 pre 0 for x in a: pre (pre x) % k ans cnt[pre] cnt[pre] 1 print(ans) if __name__ __main__: main()这里我省略了显式的前缀和数组直接用pre变量滚动记录当前前缀和对K取余的结果。因为算法每一轮只需要当前前缀和的余数不需要之前的具体数值所以不需要开一个长度为N的数组存全部前缀和。对Python这种内存敏感的语言来说省点是点。输入处理用sys.stdin.read一次性读是因为蓝桥杯有些数据量大逐行input()会慢。竞赛里这点时间差有时就是10分和0分的区别。4.2 C版本C组选手参考#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorll cnt(k, 0); cnt[0] 1; ll ans 0; ll pre 0; for (int i 0; i n; i) { ll x; cin x; pre (pre x) % k; ans cnt[pre]; cnt[pre]; } cout ans endl; return 0; }注意cnt数组的类型用了long long。虽然cnt里每个值最大也就是N10^5量级int放得下但最终ans会累加到约5×10^9int铁定溢出。这种题目一旦溢出答案就是负数或者完全错误测试点还会卡得很隐蔽不是一眼能看出来的。所以一律用long long是最稳妥的。4.3 关键易错点对照表易错点原因分析正确做法忘记cnt[0] 1s[0]0的余数是0它对应所有从a[1]开始的区间统计前先给cnt[0]赋1先cnt[pre]再ans cnt[pre]当前前缀和与自身配对形成长度为0的非法区间先累加ans再自增cntans使用intN10^5时最大答案约5×10^9超出int范围使用long longC中对负数取模如果数列含负数(-1) % K在C里可能是负数用((pre x) % k k) % kK较大时硬开数组K10^9时vector开不出来改用unordered_map计数Python里用input()逐行读大数据量下极慢用sys.stdin.read一次性读取5. 实战验证与避坑心得5.1 小数据手动验证法写完代码第一件事别急着交先用小例子手算验证。我强烈建议这个习惯从平时的练习就开始养成因为等你在赛场上没有那么多调试时间时小数据验证是你最快的自查手段。拿我们开头的例子n5, k2, a[1,2,3,4,5]按照代码逻辑cnt [0, 0]cnt[0]1 pre0 读入1pre(01)%21ans cnt[1]即0cnt[1]1 读入2pre(12)%21ans cnt[1]即1cnt[1]2 读入3pre(13)%20ans cnt[0]即1总ans2cnt[0]2 读入4pre(04)%20ans cnt[0]即2总ans4cnt[0]3 读入5pre(05)%21ans cnt[1]即2总ans6cnt[1]3最终ans6和前面手算结果完全一致。这个手动跟踪的过程实际就是在心里把整个算法又跑了一遍能帮你确认自己对每一步的理解都是对的。5.2 随机对拍用暴力程序验证正确性还有一种验证方法我每次做算法题都会用写一个O(N^2)的暴力解法再随机生成大量小数据对比暴力解和优化解的输出是否一致。这比任何人工验证都可靠因为人算容易出错随机测试可以覆盖各种边界情况。暴力代码很简单就是枚举所有区间求和def brute(a, k): n len(a) ans 0 for i in range(n): s 0 for j in range(i, n): s a[j] if s % k 0: ans 1 return ans对拍代码import random def solve(a, k): cnt [0] * k cnt[0] 1 ans 0 pre 0 for x in a: pre (pre x) % k ans cnt[pre] cnt[pre] 1 return ans for _ in range(5000): n random.randint(1, 30) k random.randint(1, 15) a [random.randint(0, 100) for _ in range(n)] if solve(a, k) ! brute(a, k): print(出错了, a, k) print(solve:, solve(a, k), brute:, brute(a, k)) break else: print(全部通过)我在这里特意把随机数范围覆盖了a[i]0的情况、k1这种极端场景。跑个几千组之后如果全部通过代码正确性就基本稳了。参赛前养成对拍习惯能在很大程度上避免“我觉得对了但交上去WA”的痛苦。5.3 从k倍区间到同类题型的迁移这个题吃透之后它的解题思路可以迁移到很多地方。最直接的是LeetCode 560题“和为K的子数组”。那个题要求区间和等于K而不是K的倍数。解法几乎一样前缀和 哈希表统计前缀和出现的次数。区别只在k倍区间统计的是余数相同的数量而560统计的是精确值相等的数量。本质上是同一个模板统计前缀和中满足某种“同余或相等”关系的配对数量。再进一步如果你遇到的是二维问题——比如“求子矩阵和是K的倍数”——那可以用二维前缀和 枚举上下边界把问题降维成多个一维k倍区间。这个变形在竞赛里也很常见。还有一种变体是K非常大的情况比如K 10^9。这时cnt数组开不出来需要对余数做哈希。Python用字典就可以C用unordered_mapfrom collections import defaultdict cnt defaultdict(int) cnt[0] 1 ans 0 pre 0 for x in a: pre (pre x) % k ans cnt[pre] cnt[pre] 1这样就把空间开销从O(K)降到了O(N)同时保持了O(N)的时间复杂度。遇到大数据范围的题目时这种弹性是必须的。另外多说一句这个问题如果放在树状数组或者线段树的场景下询问就变成了“查询当前余数区间内有多少个点”那就更进阶了但至少你现在已经知道余数统计这个基础版本是怎么回事了。6. 回到这道题本身的一些操作体感最后分享几个实操层面的体会都是我在反复做这道题、以及看别人代码时积累的碎碎念。一个是关于蓝桥杯环境的。C组提交时确保开了long long并且把ios::sync_with_stdio(false)写上。很多人的代码逻辑没问题就是输入输出拖慢了速度在大数据点上恰好卡在超时边缘。Python组则建议用sys.stdin.read批量读入别用input()逐行读。我大一第一次做这道题的时候就是因为贪方便用input()N到10^5直接卡到怀疑人生。另一个是关于读懂样例的。蓝桥杯通常会给样例输入输出但样例只是最基础的情况通过样例不代表代码没问题。你一定要自己构造几个边界小数据来验证尤其是N1只有一个数恰好是K的倍数答案应为1N1只有一个数不是K的倍数答案应为0K1所有数都是1的倍数答案是N(N1)/2全都为0所有区间和都是0都是K的倍数答案是N(N1)/2这些边界手动测一遍比什么调试技巧都管用。我后来做竞赛题养成的习惯就是任何题写完先跑这几个边界再随机对拍最后才提交。还有一点算是我个人的审美偏好这道题我最开始学的时候先用组合数公式C(cnt, 2)那种写法写了一遍又用边扫描边累加的写法写了一遍。两个都对但我后来一直用边扫描边累加的版本因为它不需要把所有前缀和先存下来空间更省代码也短。如果你第一次接触建议两种都写一遍能更深刻地理解为什么ans cnt[pre]这一步是对的、为什么累加顺序不能乱。理解了原理背代码才有意义。这道题教会我的东西其实不完全是一个算法而是一种“换个角度计数”的思维方式当直接枚举太多的时候看看能不能用数学关系把问题转化成一个统计问题。k倍区间的名字里藏着答案——前缀和负责把区间转化成差值余数统计负责把差值转化成同余配对。两板斧下来O(N^2)的问题就变成了O(N)。希望这篇文章能帮你一次把这道经典题彻底弄明白别在同样的坎上再摔第二次。