蓝桥杯有一道题只要考过算法组的同学基本都绕不过去就是K倍区间。它看起来是个“连续区间求和判断整除”的问题暴力枚举半小时就能写出来但看到n的范围是10^5就知道事情没那么简单。我第一次遇到它是在校赛热身当时还以为就是循环加判断结果超时到怀疑人生。后来弄懂“前缀和 余数统计”这个组合才明白这道题考的不是枚举而是等价变形和计数思维。这篇文章准备把这个题从题目、暴力做法、前缀和推导、同余配对、代码实现到常见坑位完整讲一遍。无论你用C、Java还是Python参加蓝桥杯核心思路完全一致。新手可以逐字看已经会做的也可以重点看后面“边界与坑位”那部分很多集训队队员也偶尔在这里翻车。1. 题目到底在问什么1.1 原题描述和数据规模直接看题面有一个长度为N的数列A1到AN现在要统计所有连续子区间[l, r]满足这个区间内所有数的和是K的整数倍。问总共有多少个这样的区间。数据范围各家略有差异蓝桥杯原题一般是N、K都不超过100000数列中的每个元素绝对值不超过10000。别小看这个绝对值条件它意味着前缀和可能是正数也可能负数后面C取模的时候要留个心眼。“是K的整数倍”这个说法很多人会把K0的情况也套进去。原题K是正整数但为了代码健壮性我会在后面的兼容写法里给出K0的处理方案。刷题平台上的测试数据偶尔会有这种边界所以防一手总没错。1.2 先试试暴力枚举最容易想到的方法就是枚举左右端点l从1到Nr从l到N每次用两层循环累加区间和判断sum % k 0计数。如果不做任何优化计算区间和还需要第三层循环那复杂度就到了O(N^3)n10^5时直接爆炸。就算先预处理一个前缀和让区间和变成O(1)查询枚举所有左右端点仍然是O(N^2)。n100000的时候区间总数约等于5.0乘以10的9次方也就是50亿哪怕每条判断只花1纳秒也要50秒。蓝桥杯单点限时一般是1秒暴力肯定不行。所以这道题必然存在一种不是枚举左右端点的统计方式。关键点在于题目只要求数量不要求具体区间这给了我们很大的优化空间。1.3 先想清楚答案会大到什么程度写这题前最好先估一下答案上界。如果K1那么所有区间都满足条件答案就是n * (n 1) / 2。n100000时大约是5,000,050,000。这个数已经超过int的上限2,147,483,647了。所以在写代码之前就知道ans必须用long long前缀和pre最好也用long long。这个预判能帮你少交一次WA。很多人逻辑全对最后挂在类型溢出上非常可惜。2. 前缀和是怎么把区间和变成减法的2.1 前缀和数组的定义前缀和是一个非常经典的预处理技巧。我们额外开一个数组prepre[i]表示原数组前i个数的总和特别地pre[0]0。递推关系就是pre[i] pre[i-1] A[i]。举个例子原数组是[1, 2, 3]那pre数组就是[0, 1, 3, 6]。这个pre[0]0不是可有可无的它代表“一个数都不取”的空前缀。后面所有边界推导都离不开它。为什么说前缀和能把区间和变成减法因为区间[l, r]的和可以看作“前r个数的总和”减去“前l-1个数的总和”。用公式写就是sum(l, r) pre[r] - pre[l-1]。这个过程相当于把原问题从区间视角切换到两个前缀和的差值视角。2.2 区间和与K的倍数怎么联系起来现在我们有pre[r]和pre[l-1]两个数。题目要求pre[r] - pre[l-1]是K的倍数。换句话说这个差值除以K的余数为0。模运算里有个基础结论如果a - b能被K整除那么a和b在模K意义下一定同余也就是a % K b % K。你甚至可以反过来理解两个具有相同余数的数它们之间相差的必然是模数的整数倍。于是原命题就等价变换了在一串前缀和pre[0], pre[1], ..., pre[n]中任取两个下标i小于j只要pre[i] % K pre[j] % K那么原数组的区间[i1, j]就是一个K倍区间。这里i的取值范围包括0也就是空前缀pre[0]也在候选人里。2.3 问题彻底变成数对数经过上面的变换题目从“枚举连续区间”变成了“从N1个前缀和中找余数相同的无序对”。N1个数取两个不同下标它们之间的顺序天然由下标决定所以实际要统计的就是有多少对(i, j)满足i j且两个前缀和余数相同。这相当于在一个数组里做“同余配对”。如果暴力地两层循环去配对依然是O(N^2)。但接下来的余数统计只需要O(N)时间这就是这道题的精华所在。从“区间”到“前缀和差分”再到“同余配对”每一步其实都是在降低维度。3. 余数统计同一个余数配对3.1 用cnt数组记录每种余数出现次数统计配对数量的常规思路是从左到右扫描每遇到一个数字先看历史上出现过多少个和它相同的数字这些历史数字都值得和当前数字配对一次然后把当前数字也计入历史。对应到本问题就是维护一个cnt数组cnt[r]表示到目前为止余数为r的前缀和个数。当我们扫描到pre[i]时假设它的余数是r那么之前已经出现过的cnt[r]个同余前缀和每一个都能和pre[i]组成一个K倍区间于是答案直接加上cnt[r]。加完之后再把pre[i]自己也放进去。这个“先查历史后更新自己”的顺序是核心。如果反过来先更新自己再查询就会把当前前缀和和自己配对产生一个不存在的空区间答案是错的。3.2 为什么cnt[0]要从1开始最大的坑点是pre[0]0也要参与计数。0对任意正整数K取模余数都是0所以cnt[0]初始值应该是1而不是0。还是用[1, 2, 3], K3来走一遍。pre数组是[0, 1, 3, 6]。正确过程是初始化cnt[0]1。i1时pre[1]%31cnt[1]为0答案加0再把cnt[1]变1。i2时pre[2]%30cnt[0]为1答案加1这个1对应区间[1,2]再把cnt[0]变2。i3时pre[3]%30cnt[0]为2答案加2这两个分别对应pre[3]和pre[0]配对出[1,2,3]pre[3]和pre[2]配对出[3]。最终答案3完整正确。如果初始cnt[0]0i2时答案加0i3时答案加1最后只得到1个区间直接少了两个。所以cnt[0]1不是可选项而是必须项。这个细节答错的人特别多很多人算法都懂就是这里漏了。3.3 另一种组合数写法除了动态扫描还有一套组合数写法先一次性统计所有pre[0]到pre[n]的余数得到cnt数组然后对每个余数r看cnt[r]里有多少个前缀和从中选两个就对应一个合法区间所以对答案的贡献是cnt[r] * (cnt[r] - 1) / 2。为什么选两个就行因为任意两个余数相同的前缀和下标小的是左端点l 小下标 1下标大的是右端点r。组合数C(cnt[r], 2)天生不区分顺序正好数的是无序对也正好就是区间。要注意cnt[0]里包含pre[0]别再多算一次。这套写法在只需要最终答案时很清爽但动态写法在代码上更直接也更好调试。两种都推荐大家掌握。4. 代码实现从C到Python4.1 C标准写法#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorlong long pre(n 1, 0); for (int i 1; i n; i) { long long x; cin x; pre[i] pre[i - 1] x; } vectorint cnt(k, 0); cnt[0] 1; long long ans 0; for (int i 1; i n; i) { int r (pre[i] % k k) % k; ans cnt[r]; cnt[r]; } cout ans \n; return 0; }这里预处理前缀和时我直接使用long long因为前缀和累加后可能超过int范围。更关键的是答案最多有大约50亿个合法区间int无论如何存不下所以ans也必须是long long。取模那行(pre[i] % k k) % k是处理负前缀和的标准写法。C的%对负数是向零取整结果可能为负加上k再取模一次就保证落在[0, k-1]。如果原数组全为正直接写pre[i] % k也没问题但写成兼容形式没有额外开销。4.2 Python实现n, k map(int, input().split()) a list(map(int, input().split())) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i] cnt {} cnt[0] 1 ans 0 for i in range(1, n 1): r pre[i] % k ans cnt.get(r, 0) cnt[r] cnt.get(r, 0) 1 print(ans)Python的%运算结果和除数同号所以pre[i]为负数时pre[i] % k也会返回非负余数这里不需要额外的修正。用字典而不是固定数组是因为如果K比较大开长度为K的列表可能会浪费内存字典只在有用余数上记录更灵活。不过要注意Python的字典查询有常数开销在n1e5时完全没问题就算n到1e6也能跑。如果K本身不大比如K100000用list代替字典会更快一些代码改成cnt [0] * k即可。4.3 Java实现简介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(); long[] pre new long[n 1]; for (int i 1; i n; i) { pre[i] pre[i - 1] sc.nextLong(); } int[] cnt new int[k]; cnt[0] 1; long ans 0; for (int i 1; i n; i) { long r (pre[i] % k k) % k; ans cnt[(int) r]; cnt[(int) r]; } System.out.println(ans); } }Java代码和C几乎一样唯一要注意的就是类型转换。cnt数组下标本身是int但pre[i]和ans要用long。很多人在Java里为了省事把pre也声明成int数据量稍大一点就会WA而且很难排查。4.4 K非常大或者K0的兼容写法如果题目改成了K最大到1e9固定数组cnt就开不下了需要用哈希表。C可以用unordered_mapint, long long cntPython直接用字典Java用HashMapLong, Long。哈希表版的动态扫描逻辑完全不变只是取值时没有默认0需要一次getOrDefault或者先判断存在。K0是比较特殊的情况此时“K的倍数”就是“0的倍数”即区间和本身为0。不能对0取模要退化成“前缀和相等”的统计问题。这个其实就是同余等价类退化成值相等仍然可以沿用哈希计数cnt {0: 1} ans 0 for i in range(1, n 1): val pre[i] ans cnt.get(val, 0) cnt[val] cnt.get(val, 0) 1原理和正常K完全一样只是把“余数相同”换成“前缀和相同”。如果你不确定平台数据里K会不会给0可以在读入K后主动分支宁可多写几行也不要运行时除零。5. 常见问题与排查技巧实录5.1 一张速查表先放在前面症状可能原因对策答案整体偏小cnt[0]没初始化成1cnt[0] 1提交后WA小样例能过答案溢出ans和pre都用long long出现数组越界或RE负数取模结果仍是负数使用(pre[i] % k k) % k答案是0但手算有结果K0取模异常特判K0按前缀和相等统计大K数据开数组爆内存cnt数组长度K太大改用哈希表这张表是我带训练营时总结出来的高频错误基本覆盖了九成以上的K倍区间提交问题。下面逐个展开讲一下。5.2 答案少了先检查cnt[0]这是最典型的错误。很多同学动态扫描时只用for i从1到n统计每个pre[i]的余数没有初始化cnt[0]1导致所有从1号位置开始的K倍区间全部被漏掉。我曾经用这个错误版跑小数据怎么都想不通为什么少算。后来把pre数组和cnt一步步打印出来才发现pre[0]根本没参与计数。所以排查时第一件事就是看cnt[0]的初始值。如果你用的是组合数写法则要看cnt[0]在统计时是否真的包含了pre[0]也就是cnt[0]至少应该是1。5.3 用int存答案导致溢出有人写C时代码逻辑全对但ans声明成int结果提交WA。原因很简单如果K1所有数都是K的倍数那么所有前缀和余数都是0cnt[0]会达到n1答案是C(n1, 2)当n100000时这个值约为50亿远超过int上限。对策前缀和pre用long long答案ans用long longcnt本身用int没问题因为最多n1个但累加ans时已经是long long运算。Java中答案类型也必须是long。5.4 取模出现负数导致cnt下标越界C中如果pre[i]可能是负数pre[i] % k会得到一个负余数直接访问cnt[r]会越界轻则WA重则RE。统一写法是int r (pre[i] % k k) % k。这一步不改变数学含义只是把余数规范化到0到k-1之间。Python没有这个问题但如果你习惯性地套C写法写成(pre[i] % k k) % k也没问题。Java同样建议用这个方法。很多蓝桥杯官方题解里写的是pre[i] % k那是默认数据全为正我自己会写兼容版避免换个平台就挂。5.5 先更新cnt还是先累加答案正确顺序是先ans cnt[r]再把cnt[r]。如果写反了会把自己算一次导致空区间计数。表面看结果可能只是多了一些但某些数据下完全对不上。另一种容易错但结果碰巧正确的情况先cnt[r]再ans cnt[r] - 1。减去1就是为了抵消自己虽然最终答案可能对但逻辑确实绕在代码review时不推荐。统一用“先查历史再更新自己”就能避免这类问题。5.6 小样本调试法我调试这个题的时候强烈建议手算下面这几组数据第一组n3, a[1,2,3], k3正确答案是3。第二组n3, a[1,2,3], k2正确答案是2。第三组n5, a[1,1,1,1,1], k2所有区间长度为偶数者满足条件一共有6个答案就是6。如果代码能通过这三个小样本基本逻辑就稳了。如果还不对就把pre和cnt在每个循环里的变化打印出来对照纸上推演。像这种“多了一个前缀和”的题打印调试比看代码快得多。6. 从K倍区间带走的通用思路6.1 前缀和哈希计数模板做完这道题你其实掌握了一套更高层的模板解决“连续子数组满足某种和条件”的问题。核心流程是三句话第一计算前缀和数组prepre[0]0不能少。第二在扫描pre[i]时计算当前需要查询的“状态量”。如果是“和能被K整除”状态量是pre[i] % K如果是“和为target”状态量是pre[i] - target如果是“和为0”状态量是pre[i]本身。第三先累加历史中相同状态量的数量到答案再把当前状态量写入历史。这套模板在LeetCode上也能对上号974题就是原封不动的同余题560题就是和为target的题。蓝桥杯近几年的前缀和混合题也经常能看到它的影子。所以K倍区间不只是一道真题更是一个通用思维模型。6.2 什么时候不能用这个模板当数组不是静态的前缀和会随着单点修改而变化那么每次查询区间和都必须重新计算静态pre数组就失效了。这种场景需要树状数组维护动态前缀和每次查询两个位置的前缀和是logN级别然后还要再考虑怎么批量统计同余对。这道题不是这种场景但如果以后扩展思路得转换。另外一个不太适用的情况是K特别大且数据范围也特别大哈希表计数虽然能用但要注意哈希冲突带来的常数问题。蓝桥杯经典题不玩这个但追求极致性能时可以手写一个简单哈希或者用数组加离散化。6.3 同余类问题的心法最后说点个人体会。K倍区间这道题真正难的不是前缀和概念而是“把区间的条件转化成前缀和的关系”这种思维跳跃。很多新手卡在为什么要核对余数甚至知道要数对却不知道P[0]怎么办。我自己第一次做的时候也是写了半天暴力最后看了题解才拍大腿。如果你现在还没完全理解我建议你拿出一张纸把pre数组写下来再在旁边列cnt的变化过程多走两个例子。越到后面你会越发觉得算法竞赛里大部分“看起来像是枚举”的题本质上都是转换成计数。前缀和、差分、哈希、同余都是在帮你压缩维度。K倍区间只是这个思维训练的起点弄清楚它对做蓝桥杯历年的许多子数组题都很有帮助。