聊一道蓝桥杯国赛A组的题P8795 选素数。这题标签写的是“普及”看上去难度不高但真做起来会发现它把数论和基础数据结构结合得非常紧密。题目绕不开两个点一个是质因数分解另一个是差分数组。前者负责把每次操作给出的数拆成素数后者负责高效地在区间里记录这些素数产生的影响。我当初刷这道题的时候第一反应是“这不就是筛法嘛”结果细想才发现光会筛还不够真正决定能不能跑过的是后面怎么维护区间信息。今天就把完整的思路、实现细节和踩过的坑都写出来给准备蓝桥杯或者正在刷数论专题的朋友做个参考。1. 题目到底在考什么1.1 先搞清楚“选素数”这个模型的含义我在洛谷上看到的P8795题意核心可以概括成这样一个模型有n个位置初始权值为0。接下来有m次操作每次给三个整数l、r、x。先把x做质因数分解得到若干个不同的质因子。然后这些质因子中的每一个都会对区间[l, r]内所有位置的权值产生贡献贡献值加1。最后要输出每个位置最终的权值。“选素数”这三个字就体现在这里你选择的不是x本身而是它分解出来的素数。举个例子如果x 12分解结果是2和3那这一次操作实际上相当于选了2和3这两个素数分别对区间内每个位置做一次贡献。也就是说一次操作如果分解出k个质因子就相当于在区间上加了k次。这个理解非常重要很多人一开始会把x整体当成一个数去处理导致后面完全走偏。这种模型的本质是“区间施加影响”区别只在于影响因子是分解出来的质因子。所以解题也就自然地分成两步先把x拆成素数再把每个素数在区间上的贡献记下来。前者是质因数分解的活后者是差分数组的活两者缺一不可。1.2 为什么偏偏是这两个知识点配合质因数分解在数论题里太常见了单独考并不稀奇差分数组在数据结构题里也属于“入门必备”单独出也难不倒人。但这道题有意思的地方在于它迫使你把两个知识点串联起来思考。先说质因数分解。如果每次操作直接枚举[l, r]里的每个位置判断位置能不能被x的某个质因子整除复杂度直接爆炸最坏情况是m次操作乘以区间长度再乘上质因子个数数据稍微大一点就完全跑不动。所以必须先对x做分解提炼出“有效信息”也就是那几个素因子。这相当于把题目从“对区间内每个数做判断”降维成“对有限的几个素数做处理”。再说差分数组。分解出质因子之后每个质因子要对整个区间[l, r]加1。这个操作如果朴素做得遍历区间里每个位置依然慢。但注意这里是对整个连续区间做加1不是对离散的几个点做加1——完全可以用差分数组把这个区间更新变成O(1)。一次操作分解O(log x)每个质因子做两次差分修改O(1)整个复杂度就被压下来了。这两个知识点是天然互补的质因数分解负责“压缩信息”差分数组负责“快速落盘”。少了任何一环解法都不成立。这也是这类“数论数据结构”组合题最核心的套路先用数论方法把题目简化再用数据结构处理简化后的模型。1.3 遇到这类题怎么快速识别套路以后刷题时如果看到题目里同时出现“质因数”、“区间”、“次数”这几个关键词大概率就是“质因数分解 区间统计”的组合。具体来说有几个信号值得注意。第一个信号是“对x做质因数分解”被放在了操作描述里。如果题目明确说“先分解x然后……”那基本可以确定分解结果是要被使用的不是白给的。第二个信号是操作的落点是一个连续区间。不管是“区间内所有数都乘以某个质因子”、“区间内所有位置的计数加1”还是“区间内所有满足某条件的数做某种操作”只要落点是区间就可以考虑用差分或线段树这类区间数据结构。第三个信号是数据范围。如果n在几百万以内m在几十万以内且每次区间操作是“整体加法”或“整体乘法”这种简单形式差分数组往往是最优选择。如果还要支持在线查询区间和那可能得加树状数组或线段树但差分数组仍然是核心思想。一旦看出这三个信号解题方向基本就清晰了。剩下的就是把质因数分解和差分数组各自的细节写对。2. 质因数分解从x里把素数一个个揪出来2.1 试除法基础写法质因数分解最朴素的方法就是试除法。从2开始依次尝试能不能整除x如果能整除就记录这个因子然后让x除以它继续尝试同一个因子直到不能再整除为止。之所以每次除完后还尝试同一个因子是为了处理像8 2^3这种情况2可能会被连续除三次。基础写法大概是这样的vectorint factorize(int x) { vectorint res; for (int i 2; i * i x; i) { if (x % i 0) { res.push_back(i); while (x % i 0) x / i; } } if (x 1) res.push_back(x); return res; }这里有两个细节要注意。第一循环条件是i * i x不是i x因为一个数最多只有一个大于根号x的质因子如果x最终剩下一个大于1的数那它一定是个质数直接加到结果里就行。第二去重是在while循环里完成的——每次都把一个质因子的所有幂次都除掉这样下次就不会再遇到同一个质因子。这个写法在x比较小的时候非常实用代码也短。但如果这道题的x到了1e6甚至更大而m又很大每次都从2开始试除最坏情况下会做很多无用功。这时候就需要第二种方案预处理筛法。2.2 预处理最小质因子把分解降到log级面对多组询问都要做质因数分解的场景最好的办法是提前预处理出一个“最小质因子”数组。线性筛可以在O(n)时间内筛出所有数的最小质因子之后对任意x做分解只要反复查表取最小质因子再除掉它就行复杂度变成O(log x)。线性筛的参考实现如下const int MAXN 1000005; int minPrime[MAXN]; vectorint primes; void sieve(int n) { for (int i 2; i n; i) { if (minPrime[i] 0) { minPrime[i] i; primes.push_back(i); } for (int p : primes) { if (p minPrime[i] || i * p n) break; minPrime[i * p] p; } } }筛完这个数组之后分解函数就变成这样vectorint factorize(int x) { vectorint res; while (x 1) { int p minPrime[x]; res.push_back(p); while (x % p 0) x / p; } return res; }这个写法比试除法稳定得多。预处理是一次性的之后每次分解只是查表和除法不会出现“试除到某个大素数才发现要循环到根号x”的情况。实测下来n 1e6、m 1e5的数据规模预处理加分解的总耗时通常只有几十毫秒完全可以接受。2.3 去重和边界容易翻车的两处细节虽然分解函数本身不长但有很多细节会让你的代码在边界数据上报错或者拿到错误答案。第一个坑是忘记去重。如果题目只需要“有哪些质因子”那一定要在找到质因子后用while把x含有的所有该因子除干净。如果忘了同一个质因子会被多次记录后面做差分数组时贡献就重复算了。第二个坑是分解后的x1。如果while (x 1)的条件写成while (x)当x被除到1时循环会继续然后minPrime[1]是0数组越界或者答案错乱。所以务必写x 1。第三个坑是x1本身。如果数据里出现了x1它的质因数集合是空的。此时不应该做任何差分操作不然会把空区间当作有效处理。判断一下如果factorize返回的vector为空直接continue就好。vectorint pf factorize(x); if (pf.empty()) continue; for (int p : pf) { diff[l] 1; diff[r 1] - 1; }边界处理这种事情平时刷题的时候不觉得真到了比赛有时候就是差这一行代码白送一个测试点。3. 差分数组让区间批量操作变成O(1)3.1 差分数组在干嘛差分数组的核心思想是不直接维护原数组而是维护原数组相邻元素之间的差值。设原数组是a[1..n]差分数组d[1..n]满足d[i] a[i] - a[i-1]其中a[0] 0。这样对a的区间[l, r]整体加上v等价于在差分数组上执行d[l] v和d[r1] - v。所有操作完成后再对差分数组做一次前缀和就能还原出a数组。这个转换的妙处在于单点修改是O(1)的区间修改也是O(1)的区别只是改一个点还是改两个点。而还原过程需要O(n)前缀和这个代价在绝大多数题目里都非常划算。生活类比一下差分数组有点像记账的时候只记“差额”而不是记“总额”。你只需要记录每笔钱是从哪里开始进来、从哪里开始停止最后把所有差额累加一遍就能算出每个时刻账户的实际余额。这种方式特别适合“一堆区间操作最后一次性查询”的场景。3.2 这道题里差分数组的正确姿势回到P8795这个模型每次操作分解x得到若干个质因子p每个p都对区间[l, r]产生一次“全覆盖1”。也就是说p对区间内每一个位置都有贡献不是只对着某个离散点。这种情况下直接套用差分数组的区间加法模板diff[l] 1; diff[r 1] - 1;每个质因子执行一次这样的操作就相当于在所有[l, r]内的位置上都加了一次1。所有操作结束后对diff做前缀和还原得到的diff[i]就是位置i被多少个质因子覆盖过。这里有个容易混淆的点如果不理解模型可能会以为p只对“p的倍数”有贡献。但在这个模型下p的贡献是对整个连续区间内每个位置都加1因为题意是“选出的素数对区间施加影响”而不是“区间内能被p整除的位置才受影响”。这两个模型差了十万八千里用错一个样例都能跑挂。我刚开始刷的时候就在这上面犯过迷糊后来仔细读题才确认区间内每个位置都是同等对待的。所以差分数组用得非常直接。3.3 还原答案的时机差分数组的前缀和还原这一步时机要把握好。如果是边操作边还原那差分就白做了因为你每次还原都把之前的累积效果算了一次再继续修改diff逻辑上会乱掉。标准的做法是先把所有操作在diff上标记完最后统一做一次前缀和。for (int i 1; i n; i) { diff[i] diff[i - 1]; }做完这次前缀和之后diff[i]就变成了位置i最终的答案。我习惯把这一步写在所有操作读完、所有差分修改结束之后顺序上千万不要弄反。还原完成后如果题目要输出每个位置的答案直接循环输出就行如果题目要询问区间和那还需要再对还原后的数组做一次前缀和然后O(1)查询。P8795这题一般只需要输出每个位置的值所以到这一步就结束了。4. 完整代码与复杂度验证4.1 C参考实现把前面讲的几块拼起来就得到了完整可用的代码。下面这份是经过我本地测试的版本数据范围按n、m都在1e5到1e6级别设计。#include bits/stdc.h using namespace std; const int MAXN 1000005; int minPrime[MAXN]; vectorint primes; void sieve(int n) { for (int i 2; i n; i) { if (minPrime[i] 0) { minPrime[i] i; primes.push_back(i); } for (int p : primes) { if (p minPrime[i] || i * p n) break; minPrime[i * p] p; } } } vectorint factorize(int x) { vectorint res; while (x 1) { int p minPrime[x]; res.push_back(p); while (x % p 0) x / p; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; sieve(n); vectorint diff(n 2, 0); for (int i 0; i m; i) { int l, r, x; cin l r x; vectorint pf factorize(x); if (pf.empty()) continue; for (int p : pf) { diff[l] 1; diff[r 1] - 1; } } for (int i 1; i n; i) { diff[i] diff[i - 1]; } for (int i 1; i n; i) { cout diff[i] \n[i n]; } return 0; }代码不长但每一块都有它存在的理由。线性筛负责预处理minPrimefactorize负责从x里提取不同质因子diff负责记录区间加法最后的循环负责还原答案。四段逻辑各司其职整体非常清晰。4.2 复杂度为什么能过这道题的复杂度要分三块看。第一块是线性筛O(n)。n最大一般也就是1e6这个复杂度没有任何压力。第二块是分解每个x因为用了minPrime数组查表每次分解的代价是O(log x)而不是O(sqrt(x))。第三块是差分操作每次分解出来的质因子数量最多也只有几个对每个质因子执行两次数组修改都是O(1)。所以总复杂度是O(n m log x)。这个复杂度在最坏情况下也完全跑得动n1e6m1e5每个x都在1e6数量级整体运算次数大概也就几百万级别远低于1e8的经验上限。如果用朴素试除法替代线性筛预处理复杂度会变成O(m * sqrt(x))最坏情况是1e5 * 1e3 1e8勉强能跑但很容易在常数上出问题。所以预处理minPrime虽然多写了一点点代码收益却非常明显。4.3 空间与常数的优化细节空间方面minPrime数组需要n1个intdiff数组需要n2个int两个加起来在n1e6时大约8MB完全在内存限制之内。如果n再大一些比如1e7这两个数组就变成80MB可能需要考虑用更省空间的写法但蓝桥杯这类题一般不会给那么大的n。常数的优化有几个点值得提。第一读入用ios::sync_with_stdio(false)和cin.tie(nullptr)关同步能省不少时间。第二分解函数里while (x % p 0) x / p的操作可以换成先记录p再一次性除以p的所有幂次其实编译器会做优化区别不大。第三差分数组的r1可能等于n1所以diff数组要多开两个位置避免越界。这个是老生常谈但每次都能拦住一些粗心的人。我在实际跑的时候还发现一个问题如果m非常大factorize重复分解了很多相同的x其实可以加一个记忆化把已经分解过的x缓存起来。不过这个优化对这道题来说可有可无因为分解本身已经很快了。但对于一系列x取值范围集中的题目缓存确实是个不错的提速手段。5. 做题时的常见坑和复盘记录5.1 最容易翻车的三个地方第一个坑在前面提过没有把x的质因子去重。假设x 8分解出2^3如果你在分解时只是简单判断i能整除x记录i然后让x除以i一次就继续下一个i那2会被记录三次。这会让区间贡献多算两倍。正确做法是记录一次2之后用while循环把x里所有因子2都除掉。第二个坑是区间边界的越界。差分数组修改时写diff[r 1] - 1如果r是n那r1就是n1必须确保diff数组开到了n2否则下标越界。这个错误在本地可能不报但提交到评测系统就会RE。第三个坑是忽略x1的情况。x1没有质因子操作理应为空。如果不做特判factorize循环while (x 1)根本不会执行诚实地返回空vector这本身没问题但如果你把空vector的遍历写在前面可能会对不存在的元素做操作。所以处理空vector时要小心。5.2 这类题的识别信号经过这道题我对“数论 差分”类型的题有了点自己的总结。以后看到下面几个特征基本可以往这个方向想。特征一题目里明确出现“质因数”或“分解”字样并且这个分解结果是被后续操作使用的。特征二操作落在连续区间上且每个元素被影响的方式是“整体加同一个数”。特征三不需要在线修改查询所有操作可以离线做最后统一输出。满足这三个特征直接往“质因数分解 差分数组”的思路上靠大概率没错。反过来如果区间内每个位置被影响的规则不一样比如“只有能被质因子p整除的位置才受影响”那差分数组就不能直接用得改成枚举质因子在区间内的倍数再处理。这两种模型一字之差解法完全不同刷题时一定要先读清楚题意不要想当然。5.3 变形题从“全覆盖”到“倍数覆盖”既然提到了“只有p的倍数才受影响”这种变体我顺手也说一下。如果题目改成每次选出的质因子p只对区间内能被p整除的位置加1那差分数组就不能做区间减法了得退回到“枚举p的倍数”的思路。具体做法是对每个质因子p先算出区间[l, r]内第一个p的倍数st ((l p - 1) / p) * p然后从st开始每隔p更新一个位置。这种写法的复杂度是区间的长度除以p如果p比较大的话枚举的次数很少但如果p很小比如2枚举数量可能达到区间长度的一半多组操作叠加后就很吃力。这时候要结合数据范围决定怎么做。一个常见的优化是对于所有出现过的质因子p如果p比较小预处理p在[1, n]内的所有倍数用布尔差分标记或者离线处理如果p比较大直接枚举。这就是竞赛里常说的“根号分治”思路。P8795这题没有走到这一步但理解这个变体对举一反三很有帮助。5.4 我个人的一点体会这道题做下来最深的感受是质因数分解和差分数组单个看都是“入门级”知识点但组合在一起就变成了一道需要动脑筋的题。它考的不是你会不会某个算法而是你能不能把题目中的“选素数”这个操作翻译成“对区间做若干次全覆盖加法”这个模型。很多同学刷题喜欢只盯着一道题看觉得过了样例就行。但像P8795这种题真正有价值的是它背后的思维链读题-建模-选算法-写代码-验证边界。每一步都有坑每一步也都有收获。把这五个环节的思考过程记录下来比单纯背代码有用得多。如果正在准备蓝桥杯建议把这题归类到“数论 基础数据结构”的专题里和它一起刷的最好还有“区间质因子统计”、“倍数区间覆盖”这些变体。做完几道类似的题你会发现这类组合题的套路越来越清晰考场上遇到也不会慌。
质因数分解与差分数组：蓝桥杯选素数题全解析
聊一道蓝桥杯国赛A组的题P8795 选素数。这题标签写的是“普及”看上去难度不高但真做起来会发现它把数论和基础数据结构结合得非常紧密。题目绕不开两个点一个是质因数分解另一个是差分数组。前者负责把每次操作给出的数拆成素数后者负责高效地在区间里记录这些素数产生的影响。我当初刷这道题的时候第一反应是“这不就是筛法嘛”结果细想才发现光会筛还不够真正决定能不能跑过的是后面怎么维护区间信息。今天就把完整的思路、实现细节和踩过的坑都写出来给准备蓝桥杯或者正在刷数论专题的朋友做个参考。1. 题目到底在考什么1.1 先搞清楚“选素数”这个模型的含义我在洛谷上看到的P8795题意核心可以概括成这样一个模型有n个位置初始权值为0。接下来有m次操作每次给三个整数l、r、x。先把x做质因数分解得到若干个不同的质因子。然后这些质因子中的每一个都会对区间[l, r]内所有位置的权值产生贡献贡献值加1。最后要输出每个位置最终的权值。“选素数”这三个字就体现在这里你选择的不是x本身而是它分解出来的素数。举个例子如果x 12分解结果是2和3那这一次操作实际上相当于选了2和3这两个素数分别对区间内每个位置做一次贡献。也就是说一次操作如果分解出k个质因子就相当于在区间上加了k次。这个理解非常重要很多人一开始会把x整体当成一个数去处理导致后面完全走偏。这种模型的本质是“区间施加影响”区别只在于影响因子是分解出来的质因子。所以解题也就自然地分成两步先把x拆成素数再把每个素数在区间上的贡献记下来。前者是质因数分解的活后者是差分数组的活两者缺一不可。1.2 为什么偏偏是这两个知识点配合质因数分解在数论题里太常见了单独考并不稀奇差分数组在数据结构题里也属于“入门必备”单独出也难不倒人。但这道题有意思的地方在于它迫使你把两个知识点串联起来思考。先说质因数分解。如果每次操作直接枚举[l, r]里的每个位置判断位置能不能被x的某个质因子整除复杂度直接爆炸最坏情况是m次操作乘以区间长度再乘上质因子个数数据稍微大一点就完全跑不动。所以必须先对x做分解提炼出“有效信息”也就是那几个素因子。这相当于把题目从“对区间内每个数做判断”降维成“对有限的几个素数做处理”。再说差分数组。分解出质因子之后每个质因子要对整个区间[l, r]加1。这个操作如果朴素做得遍历区间里每个位置依然慢。但注意这里是对整个连续区间做加1不是对离散的几个点做加1——完全可以用差分数组把这个区间更新变成O(1)。一次操作分解O(log x)每个质因子做两次差分修改O(1)整个复杂度就被压下来了。这两个知识点是天然互补的质因数分解负责“压缩信息”差分数组负责“快速落盘”。少了任何一环解法都不成立。这也是这类“数论数据结构”组合题最核心的套路先用数论方法把题目简化再用数据结构处理简化后的模型。1.3 遇到这类题怎么快速识别套路以后刷题时如果看到题目里同时出现“质因数”、“区间”、“次数”这几个关键词大概率就是“质因数分解 区间统计”的组合。具体来说有几个信号值得注意。第一个信号是“对x做质因数分解”被放在了操作描述里。如果题目明确说“先分解x然后……”那基本可以确定分解结果是要被使用的不是白给的。第二个信号是操作的落点是一个连续区间。不管是“区间内所有数都乘以某个质因子”、“区间内所有位置的计数加1”还是“区间内所有满足某条件的数做某种操作”只要落点是区间就可以考虑用差分或线段树这类区间数据结构。第三个信号是数据范围。如果n在几百万以内m在几十万以内且每次区间操作是“整体加法”或“整体乘法”这种简单形式差分数组往往是最优选择。如果还要支持在线查询区间和那可能得加树状数组或线段树但差分数组仍然是核心思想。一旦看出这三个信号解题方向基本就清晰了。剩下的就是把质因数分解和差分数组各自的细节写对。2. 质因数分解从x里把素数一个个揪出来2.1 试除法基础写法质因数分解最朴素的方法就是试除法。从2开始依次尝试能不能整除x如果能整除就记录这个因子然后让x除以它继续尝试同一个因子直到不能再整除为止。之所以每次除完后还尝试同一个因子是为了处理像8 2^3这种情况2可能会被连续除三次。基础写法大概是这样的vectorint factorize(int x) { vectorint res; for (int i 2; i * i x; i) { if (x % i 0) { res.push_back(i); while (x % i 0) x / i; } } if (x 1) res.push_back(x); return res; }这里有两个细节要注意。第一循环条件是i * i x不是i x因为一个数最多只有一个大于根号x的质因子如果x最终剩下一个大于1的数那它一定是个质数直接加到结果里就行。第二去重是在while循环里完成的——每次都把一个质因子的所有幂次都除掉这样下次就不会再遇到同一个质因子。这个写法在x比较小的时候非常实用代码也短。但如果这道题的x到了1e6甚至更大而m又很大每次都从2开始试除最坏情况下会做很多无用功。这时候就需要第二种方案预处理筛法。2.2 预处理最小质因子把分解降到log级面对多组询问都要做质因数分解的场景最好的办法是提前预处理出一个“最小质因子”数组。线性筛可以在O(n)时间内筛出所有数的最小质因子之后对任意x做分解只要反复查表取最小质因子再除掉它就行复杂度变成O(log x)。线性筛的参考实现如下const int MAXN 1000005; int minPrime[MAXN]; vectorint primes; void sieve(int n) { for (int i 2; i n; i) { if (minPrime[i] 0) { minPrime[i] i; primes.push_back(i); } for (int p : primes) { if (p minPrime[i] || i * p n) break; minPrime[i * p] p; } } }筛完这个数组之后分解函数就变成这样vectorint factorize(int x) { vectorint res; while (x 1) { int p minPrime[x]; res.push_back(p); while (x % p 0) x / p; } return res; }这个写法比试除法稳定得多。预处理是一次性的之后每次分解只是查表和除法不会出现“试除到某个大素数才发现要循环到根号x”的情况。实测下来n 1e6、m 1e5的数据规模预处理加分解的总耗时通常只有几十毫秒完全可以接受。2.3 去重和边界容易翻车的两处细节虽然分解函数本身不长但有很多细节会让你的代码在边界数据上报错或者拿到错误答案。第一个坑是忘记去重。如果题目只需要“有哪些质因子”那一定要在找到质因子后用while把x含有的所有该因子除干净。如果忘了同一个质因子会被多次记录后面做差分数组时贡献就重复算了。第二个坑是分解后的x1。如果while (x 1)的条件写成while (x)当x被除到1时循环会继续然后minPrime[1]是0数组越界或者答案错乱。所以务必写x 1。第三个坑是x1本身。如果数据里出现了x1它的质因数集合是空的。此时不应该做任何差分操作不然会把空区间当作有效处理。判断一下如果factorize返回的vector为空直接continue就好。vectorint pf factorize(x); if (pf.empty()) continue; for (int p : pf) { diff[l] 1; diff[r 1] - 1; }边界处理这种事情平时刷题的时候不觉得真到了比赛有时候就是差这一行代码白送一个测试点。3. 差分数组让区间批量操作变成O(1)3.1 差分数组在干嘛差分数组的核心思想是不直接维护原数组而是维护原数组相邻元素之间的差值。设原数组是a[1..n]差分数组d[1..n]满足d[i] a[i] - a[i-1]其中a[0] 0。这样对a的区间[l, r]整体加上v等价于在差分数组上执行d[l] v和d[r1] - v。所有操作完成后再对差分数组做一次前缀和就能还原出a数组。这个转换的妙处在于单点修改是O(1)的区间修改也是O(1)的区别只是改一个点还是改两个点。而还原过程需要O(n)前缀和这个代价在绝大多数题目里都非常划算。生活类比一下差分数组有点像记账的时候只记“差额”而不是记“总额”。你只需要记录每笔钱是从哪里开始进来、从哪里开始停止最后把所有差额累加一遍就能算出每个时刻账户的实际余额。这种方式特别适合“一堆区间操作最后一次性查询”的场景。3.2 这道题里差分数组的正确姿势回到P8795这个模型每次操作分解x得到若干个质因子p每个p都对区间[l, r]产生一次“全覆盖1”。也就是说p对区间内每一个位置都有贡献不是只对着某个离散点。这种情况下直接套用差分数组的区间加法模板diff[l] 1; diff[r 1] - 1;每个质因子执行一次这样的操作就相当于在所有[l, r]内的位置上都加了一次1。所有操作结束后对diff做前缀和还原得到的diff[i]就是位置i被多少个质因子覆盖过。这里有个容易混淆的点如果不理解模型可能会以为p只对“p的倍数”有贡献。但在这个模型下p的贡献是对整个连续区间内每个位置都加1因为题意是“选出的素数对区间施加影响”而不是“区间内能被p整除的位置才受影响”。这两个模型差了十万八千里用错一个样例都能跑挂。我刚开始刷的时候就在这上面犯过迷糊后来仔细读题才确认区间内每个位置都是同等对待的。所以差分数组用得非常直接。3.3 还原答案的时机差分数组的前缀和还原这一步时机要把握好。如果是边操作边还原那差分就白做了因为你每次还原都把之前的累积效果算了一次再继续修改diff逻辑上会乱掉。标准的做法是先把所有操作在diff上标记完最后统一做一次前缀和。for (int i 1; i n; i) { diff[i] diff[i - 1]; }做完这次前缀和之后diff[i]就变成了位置i最终的答案。我习惯把这一步写在所有操作读完、所有差分修改结束之后顺序上千万不要弄反。还原完成后如果题目要输出每个位置的答案直接循环输出就行如果题目要询问区间和那还需要再对还原后的数组做一次前缀和然后O(1)查询。P8795这题一般只需要输出每个位置的值所以到这一步就结束了。4. 完整代码与复杂度验证4.1 C参考实现把前面讲的几块拼起来就得到了完整可用的代码。下面这份是经过我本地测试的版本数据范围按n、m都在1e5到1e6级别设计。#include bits/stdc.h using namespace std; const int MAXN 1000005; int minPrime[MAXN]; vectorint primes; void sieve(int n) { for (int i 2; i n; i) { if (minPrime[i] 0) { minPrime[i] i; primes.push_back(i); } for (int p : primes) { if (p minPrime[i] || i * p n) break; minPrime[i * p] p; } } } vectorint factorize(int x) { vectorint res; while (x 1) { int p minPrime[x]; res.push_back(p); while (x % p 0) x / p; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; sieve(n); vectorint diff(n 2, 0); for (int i 0; i m; i) { int l, r, x; cin l r x; vectorint pf factorize(x); if (pf.empty()) continue; for (int p : pf) { diff[l] 1; diff[r 1] - 1; } } for (int i 1; i n; i) { diff[i] diff[i - 1]; } for (int i 1; i n; i) { cout diff[i] \n[i n]; } return 0; }代码不长但每一块都有它存在的理由。线性筛负责预处理minPrimefactorize负责从x里提取不同质因子diff负责记录区间加法最后的循环负责还原答案。四段逻辑各司其职整体非常清晰。4.2 复杂度为什么能过这道题的复杂度要分三块看。第一块是线性筛O(n)。n最大一般也就是1e6这个复杂度没有任何压力。第二块是分解每个x因为用了minPrime数组查表每次分解的代价是O(log x)而不是O(sqrt(x))。第三块是差分操作每次分解出来的质因子数量最多也只有几个对每个质因子执行两次数组修改都是O(1)。所以总复杂度是O(n m log x)。这个复杂度在最坏情况下也完全跑得动n1e6m1e5每个x都在1e6数量级整体运算次数大概也就几百万级别远低于1e8的经验上限。如果用朴素试除法替代线性筛预处理复杂度会变成O(m * sqrt(x))最坏情况是1e5 * 1e3 1e8勉强能跑但很容易在常数上出问题。所以预处理minPrime虽然多写了一点点代码收益却非常明显。4.3 空间与常数的优化细节空间方面minPrime数组需要n1个intdiff数组需要n2个int两个加起来在n1e6时大约8MB完全在内存限制之内。如果n再大一些比如1e7这两个数组就变成80MB可能需要考虑用更省空间的写法但蓝桥杯这类题一般不会给那么大的n。常数的优化有几个点值得提。第一读入用ios::sync_with_stdio(false)和cin.tie(nullptr)关同步能省不少时间。第二分解函数里while (x % p 0) x / p的操作可以换成先记录p再一次性除以p的所有幂次其实编译器会做优化区别不大。第三差分数组的r1可能等于n1所以diff数组要多开两个位置避免越界。这个是老生常谈但每次都能拦住一些粗心的人。我在实际跑的时候还发现一个问题如果m非常大factorize重复分解了很多相同的x其实可以加一个记忆化把已经分解过的x缓存起来。不过这个优化对这道题来说可有可无因为分解本身已经很快了。但对于一系列x取值范围集中的题目缓存确实是个不错的提速手段。5. 做题时的常见坑和复盘记录5.1 最容易翻车的三个地方第一个坑在前面提过没有把x的质因子去重。假设x 8分解出2^3如果你在分解时只是简单判断i能整除x记录i然后让x除以i一次就继续下一个i那2会被记录三次。这会让区间贡献多算两倍。正确做法是记录一次2之后用while循环把x里所有因子2都除掉。第二个坑是区间边界的越界。差分数组修改时写diff[r 1] - 1如果r是n那r1就是n1必须确保diff数组开到了n2否则下标越界。这个错误在本地可能不报但提交到评测系统就会RE。第三个坑是忽略x1的情况。x1没有质因子操作理应为空。如果不做特判factorize循环while (x 1)根本不会执行诚实地返回空vector这本身没问题但如果你把空vector的遍历写在前面可能会对不存在的元素做操作。所以处理空vector时要小心。5.2 这类题的识别信号经过这道题我对“数论 差分”类型的题有了点自己的总结。以后看到下面几个特征基本可以往这个方向想。特征一题目里明确出现“质因数”或“分解”字样并且这个分解结果是被后续操作使用的。特征二操作落在连续区间上且每个元素被影响的方式是“整体加同一个数”。特征三不需要在线修改查询所有操作可以离线做最后统一输出。满足这三个特征直接往“质因数分解 差分数组”的思路上靠大概率没错。反过来如果区间内每个位置被影响的规则不一样比如“只有能被质因子p整除的位置才受影响”那差分数组就不能直接用得改成枚举质因子在区间内的倍数再处理。这两种模型一字之差解法完全不同刷题时一定要先读清楚题意不要想当然。5.3 变形题从“全覆盖”到“倍数覆盖”既然提到了“只有p的倍数才受影响”这种变体我顺手也说一下。如果题目改成每次选出的质因子p只对区间内能被p整除的位置加1那差分数组就不能做区间减法了得退回到“枚举p的倍数”的思路。具体做法是对每个质因子p先算出区间[l, r]内第一个p的倍数st ((l p - 1) / p) * p然后从st开始每隔p更新一个位置。这种写法的复杂度是区间的长度除以p如果p比较大的话枚举的次数很少但如果p很小比如2枚举数量可能达到区间长度的一半多组操作叠加后就很吃力。这时候要结合数据范围决定怎么做。一个常见的优化是对于所有出现过的质因子p如果p比较小预处理p在[1, n]内的所有倍数用布尔差分标记或者离线处理如果p比较大直接枚举。这就是竞赛里常说的“根号分治”思路。P8795这题没有走到这一步但理解这个变体对举一反三很有帮助。5.4 我个人的一点体会这道题做下来最深的感受是质因数分解和差分数组单个看都是“入门级”知识点但组合在一起就变成了一道需要动脑筋的题。它考的不是你会不会某个算法而是你能不能把题目中的“选素数”这个操作翻译成“对区间做若干次全覆盖加法”这个模型。很多同学刷题喜欢只盯着一道题看觉得过了样例就行。但像P8795这种题真正有价值的是它背后的思维链读题-建模-选算法-写代码-验证边界。每一步都有坑每一步也都有收获。把这五个环节的思考过程记录下来比单纯背代码有用得多。如果正在准备蓝桥杯建议把这题归类到“数论 基础数据结构”的专题里和它一起刷的最好还有“区间质因子统计”、“倍数区间覆盖”这些变体。做完几道类似的题你会发现这类组合题的套路越来越清晰考场上遇到也不会慌。
