企业官网建设流程全解析

聊一道蓝桥杯国赛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可能会被连续除三次。

基础写法大概是这样的：

vector<int> factorize(int x) { vector<int> 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]; vector<int> 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; } } }

筛完这个数组之后，分解函数就变成这样：

vector<int> factorize(int x) { vector<int> 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含有的所有该因子除干净。如果忘了，同一个质因子会被多次记录，后面做差分数组时贡献就重复算了。

第二个坑是分解后的x=1。如果while (x > 1)的条件写成while (x)，当x被除到1时循环会继续，然后minPrime[1]是0，数组越界或者答案错乱。所以务必写x > 1。

第三个坑是x=1本身。如果数据里出现了x=1，它的质因数集合是空的。此时不应该做任何差分操作，不然会把空区间当作有效处理。判断一下，如果factorize返回的vector为空，直接continue就好。

vector<int> 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[r+1] -= 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]; vector<int> 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; } } } vector<int> factorize(int x) { vector<int> 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); vector<int> diff(n + 2, 0); for (int i = 0; i < m; i++) { int l, r, x; cin >> l >> r >> x; vector<int> 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; }

代码不长，但每一块都有它存在的理由。线性筛负责预处理minPrime，factorize负责从x里提取不同质因子，diff负责记录区间加法，最后的循环负责还原答案。四段逻辑各司其职，整体非常清晰。

4.2 复杂度为什么能过

这道题的复杂度要分三块看。

第一块是线性筛，O(n)。n最大一般也就是1e6，这个复杂度没有任何压力。第二块是分解每个x，因为用了minPrime数组查表，每次分解的代价是O(log x)，而不是O(sqrt(x))。第三块是差分操作，每次分解出来的质因子数量最多也只有几个，对每个质因子执行两次数组修改，都是O(1)。所以总复杂度是O(n + m log x)。

这个复杂度在最坏情况下也完全跑得动：n=1e6，m=1e5，每个x都在1e6数量级，整体运算次数大概也就几百万级别，远低于1e8的经验上限。

如果用朴素试除法替代线性筛预处理，复杂度会变成O(m * sqrt(x))，最坏情况是1e5 * 1e3 = 1e8，勉强能跑，但很容易在常数上出问题。所以预处理minPrime虽然多写了一点点代码，收益却非常明显。

4.3 空间与常数的优化细节

空间方面，minPrime数组需要n+1个int，diff数组需要n+2个int，两个加起来在n=1e6时大约8MB，完全在内存限制之内。如果n再大一些，比如1e7，这两个数组就变成80MB，可能需要考虑用更省空间的写法，但蓝桥杯这类题一般不会给那么大的n。

常数的优化有几个点值得提。第一，读入用ios::sync_with_stdio(false)和cin.tie(nullptr)关同步，能省不少时间。第二，分解函数里while (x % p == 0) x /= p的操作可以换成先记录p，再一次性除以p的所有幂次，其实编译器会做优化，区别不大。第三，差分数组的r+1可能等于n+1，所以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，那r+1就是n+1，必须确保diff数组开到了n+2，否则下标越界。这个错误在本地可能不报，但提交到评测系统就会RE。

第三个坑是忽略x=1的情况。x=1没有质因子，操作理应为空。如果不做特判，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这种题，真正有价值的是它背后的思维链：读题-建模-选算法-写代码-验证边界。每一步都有坑，每一步也都有收获。把这五个环节的思考过程记录下来，比单纯背代码有用得多。

如果正在准备蓝桥杯，建议把这题归类到“数论 + 基础数据结构”的专题里，和它一起刷的，最好还有“区间质因子统计”、“倍数区间覆盖”这些变体。做完几道类似的题，你会发现这类组合题的套路越来越清晰，考场上遇到也不会慌。