1. 题目到底在问什么先读懂 P8795 的题意1.1 题目背景与读题要点这道题是 2022 年蓝桥杯国赛 A 组的题目题号 P8795名字叫“选素数”难度标的是“普及”。很多同学看到“数论”“质因数分解”“差分数组”这三个标签凑在一起就先慌了其实拆开来看每一步都不算难难点在于你能不能把这些知识点串起来。先说结论这道题本质上是一个“区间覆盖计数”问题质因数分解只是用来生成区间的工具差分数组才是真正干活的家伙。题目的大意是有一个初始整数你可以进行若干次操作每次操作是先选一个当前数的大于 1 的因子注意这里说的是选一个因子然后把这个因子加到当前数上得到新的数。给你一个区间[L, R]问你从某个初始值出发经过恰好一次操作后能落在区间[L, R]内的初始值有多少个。这里有个非常关键的细节题目里说的“因子”到底是什么意思很多人下意识以为是质因子但其实是“任意大于 1 的因子”。比如当前数是 6你可以选 2、3、6分别得到 8、9、12。当然我们后续推导会发现为了最大化覆盖范围真正需要考虑的其实只有质因子带来的影响但读题时不能先入为主否则容易漏情况。1.2 输入输出与数据范围分析输入格式给的是一个闭区间[L, R]输出是满足条件的初始值个数。数据范围我记得是1 L R 10^6级别具体数值可能不同题解版本略有差异但基本都是百万级别。这个范围意味着两件事第一不能开O(n^2)的循环比如枚举每个初始值再枚举所有因子那肯定是超时的百万的平方是十万亿神仙也跑不完。第二O(n log n)甚至O(n sqrt(n))的算法是可接受的。因为百万级别的sqrt(n)是一千一千万次操作勉强能过如果常数小一点也能接受。但更优雅的做法是筛法预处理把所有数的质因子提前筛出来然后配合差分数组做到接近线性的复杂度。所以看到百万数据一个合格选手的直觉应该是这题八成要用线性或接近线性的算法。差分数组恰好是处理区间批量加法的利器而质因数分解则负责告诉我们“哪些初始值能通过某次操作到达某个目标数”。这两者是怎么结合的呢下面逐步拆解。2. 从朴素做法到正解为什么是质因数分解 差分数组2.1 朴素模拟为什么不行先想想最直接的思路枚举每一个可能的初始值x枚举x的所有大于 1 的因子d判断x d是否落在[L, R]内是则答案加一。这个逻辑本身没问题但复杂度是O(n * tau(n))tau(n)是因子个数。最坏情况下一个数的因子个数能达到几百百万个数枚举下来就是上亿次操作而且每次还要做除法判因子常数很大大概率超时。更重要的是这种枚举方式没有利用题目中“区间连续”的特点。如果我们能反过来思考对于区间内的每个目标数y能不能找出所有能一步到达y的初始值x如果能批量处理这些x就可以用差分数组一次性标记那效率就完全不一样了。于是核心问题变成了给定目标数y哪些x满足x d y其中d是x的一个大于 1 的因子稍微变个形d y - x且d是x的因子也就是说d能整除x。又因为y x d所以d也能整除y。这个推导非常关键d同时是x和y的因子而且x y - d。也就是说对于每个目标数y我们只需要枚举y的某个因子d令x y - d然后检查d是否是x的因子即可。这样依然要枚举因子但复杂度从“枚举所有数”变成了“枚举区间内每个数的因子”整体差不多是O(n sqrt(n))量级百万数据勉强可跑但还可以优化。2.2 核心观察一次操作的本质继续深挖如果d同时是x和y的因子那d必然是gcd(x, y)的因子。但这里更漂亮的性质是因为y x d所以y和x关于d同余即y ≡ x (mod d)。而d又能整除x所以x ≡ 0 (mod d)推出y ≡ 0 (mod d)也就是d整除y这和上面结论一致。那我们能不能进一步缩小枚举范围注意到d 1且d x因为因子不能超过本身所以x y - d 1即d y - 1。又因为d是y的因子所以每个目标数y最多有tau(y)个候选d。枚举每个y的因子判断对应x是否满足d | x复杂度大概是O(R sqrt(R))。百万数据下大概是十亿次操作常数压一压可能过但不够优雅。更加关键的性质是其实我们只需要考虑d是y的质因子或质因子的倍数吗不对这里有个经典结论如果d是x的因子且y x d那么d一定可以取为y的某个因子。但进一步想当d含有多个质因子时效果会被“拆分”成更小的步骤覆盖吗题目要求恰好一次操作所以不能拆。那能不能只枚举质因子呢要小心。举个例子x 4因子有 2、4。取d2得到y6取d4得到y8。对于y8它的因子有 2、4、8其中d4满足条件。如果只枚举y8的质因子 2那x6但2不是6的因子实际上 2 是 6 的因子所以也算一种情况。但d8时x0不合法。所以这个例子说明d不一定是质因子但由y的因子构成。因此最稳妥的办法还是枚举y的所有因子。不过在实际代码中可以枚举y的所有真因子逐个验证。百万范围内总因子个数大约是n log n级别的期望用筛法预处理每个数的因子列表内存可能爆炸但用枚举到sqrt(y)的方式实现简单、够用。2.3 差分数组如何派上用场假设我们已经遍历到了目标数y找到了一组合法的(x, d)那么意味着初始值x经过一次操作可以到达y。如果y在区间[L, R]内那x就是一个候选答案。注意同一个x可能对应多个不同的y但我们只关心“是否存在至少一个y在[L, R]内”所以计数时不能重复。差分数组的思路是对于每一个x我们想知道它是否被至少一个合法目标覆盖。如果我们能生成一系列“区间”表示哪些x能到达某个y那就可以用差分批量加一。但这里每个y对应的x不是连续的而是一些离散的点。不过我们可以换个角度思考对于固定的d满足条件的x必须满足x ≡ 0 (mod d)且y x d落在[L, R]内。反过来对每个可能的d所有满足y ∈ [L, R]且d | y的y对应x y - d。这些x构成一个等差数列x k*d - d (k-1)*d。也就是说对于固定的d所有合法的x是d的倍数且对应的y x d在区间内即x ∈ [L - d, R - d]并且x是d的倍数。这不就是一个区间内等差数列的标记问题吗于是可以用差分数组处理对于每个可能的d我们找到区间[L-d, R-d]内所有d的倍数并在差分数组上对这些位置加 1。但这样要枚举所有d而d的范围是2 ~ R直接枚举是不行的因为d的个数是百万级每个还要处理区间内所有倍数总复杂度是O(R log R)勉强可以接受。但这里有个前提d必须是目标数y的因子而不是任意数。如果盲目枚举所有d会把大量不合法的情况算进去导致重复计数。所以需要结合刚才的发现d必须是y的因子而y x d所以d必须满足存在y ∈ [L, R]使得d | y。这个循环依赖比较棘手。换个更直接的做法从每个目标数y出发枚举它的所有因子d得到x y - d然后在差分数组的x位置加 1或者用一个布尔数组标记。最后统计有多少个x被标记过。这样做的好处是逻辑直观每个y只枚举它的真因子复杂度O(R sqrt(R))对于百万范围可过。但还有一个隐藏问题同一个x可能被多个y标记但题目只计数一次。如果用差分数组的传统“区间加”那是为了处理连续区间而这里是离散的点所以直接用布尔数组或者计数数组即可最终统计计数大于 0 的位置个数。看到这里你可能会问那差分数组到底用在哪别急还有更优的解法。真正的正解往往是对d而不是对y下手。因为d必须是某个y的因子也就是说d本身可以是任意大于 1 的整数只要存在y在[L, R]内且是d的倍数。于是我们可以枚举d找到区间内所有d的倍数y则x y - d。这些x构成了一个等差数列但每个d可能会对应多个y。此时我们可以把这些x的位置全部加 1。如果直接用循环加每个d要处理(R-L)/d个点总复杂度是调和级数O(R log R)非常优秀。但前提是每个d都必须被考虑到吗是的因为任意一个合法的(x, d)都满足d是某个y x d的因子也就是说只要我们枚举所有d对每个d枚举区间内所有y ≡ 0 (mod d)就一定能覆盖所有合法情况。关键就在这里我们不再需要枚举y的因子而是改成枚举d的所有倍数。这正好和筛法的思想一致复杂度从O(R sqrt(R))降到O(R log R)而且差分数组在这里就可以派上用场了——不对这里用的是“计数数组直接加一”并不是区间加。差分数组的用处体现在另一个变种如果题目问的是“连续一段区间内的初始值”我们也可以把每个x的贡献转为对差分数组的单点操作最终前缀和得到每个位置是否合法。但本质上这里用到的只是“单点标记累加”差分数组的前缀和步骤可有可无。那为什么题解里普遍提到“差分数组”因为有一种更妙的转换对于每个d所有合法的x构成等差数列x k*d其中k 1,2,...并且x的取值范围是[L-d, R-d]。如果我们想要快速知道某个x是否被覆盖可以直接用差分标记每个满足条件的x位置加 1。但如果d很大区间内可能只有一个或零个倍数单点操作即可如果d很小区间内有很多倍数需要循环加。总复杂度依然是O(R log R)。实际上没有必要用差分做区间加因为每个贡献点不是一段连续区间而是等差数列。所以很多题解里写的“差分数组”可能是指用差分数组来避免对每个x多次造成的多次遍历不对单点加本身就是 O(1)。我猜测题解中的“差分数组”更可能是指对每个d我们在整个值域上把满足条件的x全部加 1最终通过前缀和还原出每个位置被覆盖的次数。这个过程中单点加可以直接操作一个数组并不需要差分。但如果要把所有满足条件的x一次性表示成连续区间那只有一种特殊情况当d1时x可以是连续区间但d1不符合因子大于 1 的条件。所以这里确实不是传统意义下的区间差分。不过另一种更常规的做法确实是差分数组对每个质数p的幂或者每个因子d我们可以找到一组连续的x区间仔细想想如果固定dy取区间内所有d的倍数那么x y - d也是一组离散点每两个相邻点之间间隔d。这些点不连续无法用一次区间加表示。但如果我们枚举的不是d而是x的质因子呢比如对于每个初始值x它能到达的数y x d其中d是任意因子。如果我们反过来对于每个y所有能到达它的x是y - d其中d是y的因子。这些x也离散。所以这个题目里差分数组的用法我倾向于认为是在预处理每个数的“合法初始值”时使用差分数组来批量标记“所有因子为某个值的数”。比如我们想对所有x标记出“存在一个因子d使得xd在区间内”这等价于对每个d在x k*d的位置上加 1前提是xd在区间内。我们可以开一个差分数组diff对每个d找出x的最小值和最大值即l max(1, L-d)r R-d然后我们要在区间[l, r]中所有d的倍数位置加 1。对于等差序列如果我们想快速给所有d的倍数加 1可以采用“差分之差分”或者直接循环跳着加。由于每个d的倍数个数是(r-l)/d总复杂度是调和级数O(R log R)这已经足够。所以实际代码中直接用一个cnt数组然后循环加即可不需要差分。但“差分数组”这个标签可能是为了强调用diff[x]和diff[x1]--这种技巧来处理单点标记后统一求前缀和实际上单点标记直接cnt[x]就行没必要差分。这里我给出一个更合理的解释有的做法是先枚举所有可能的d然后对于每个d把对应的所有x在差分数组上标记为“覆盖一次”。如果后期还要统计某个区间内有多少个合法初始值那么单点cnt[x]后做前缀和本质上等价于对差分数组的diff[x]和diff[x1]--再还原。所以“差分数组”可能只是指“利用差分思想对值域进行批量统计”的一种表述实际实现时可以灵活处理。我会在代码中直接使用cnt数组简洁明了。3. 完整解题流程与代码实现3.1 分解质因数的高效写法虽然最终方案可以不用显式分解质因数但为了严谨还是先说下分解质因数的常用写法。对于单个n用试除法到sqrt(n)即可vectorint factor(int n) { vectorint res; for (int i 2; i * i n; i) { if (n % i 0) { res.push_back(i); while (n % i 0) n / i; } } if (n 1) res.push_back(n); return res; }注意这里存的是质因子而不是所有因子。如果要枚举所有因子需要从质因子组合得到。但下面我会展示一种不需要枚举所有因子的做法直接用倍数枚举会更简单。3.2 用倍数枚举替代因子枚举核心思路是枚举每个可能的操作增量d即因子然后找出所有满足条件的初始值x。条件是x 0d是x的因子且y x d在[L, R]内。从y的角度看对于每个y ∈ [L, R]枚举y的所有因子d得到x y - d然后判断d是否是x的因子。这个判断可以简化为因为d | y且y x d所以d | x等价于d | (y - d)而d | y时d | (y - d)显然成立。所以实际上只要d | y那么d就自动是x y - d的因子我们来验证设y k*d则x k*d - d (k-1)*d显然d | x。所以这是一个必然成立的条件也就是说只要y是d的倍数那么x y - d一定满足d | x并且x d y。这太关键了完全不需要额外的因子判断。那么合法条件简化为枚举所有d 2对所有满足y ∈ [L, R]且y % d 0的yx y - d就是一个合法的初始值。注意x必须大于 0即y - d 1所以y d。由于y是d的倍数最小的y就是d本身此时x 0不合法所以要从2*d开始取。另外x不能超过R其实x只要满足x d y且y R那么x R - d R所以 x 自然在值域内。但题目要求的是初始值初始值本身没有范围限制吗数据范围一般会说初始值也满足某个范围比如1 x R通常初始值也限定在[1, R]内因为如果初始值大于 R那加上一个正因子更大于 R不可能落到[L, R]所以不用考虑。因此我们只需考虑x 1且x R。所以具体做法读入L, R。初始化一个标记数组vis大小为R 2全部为false表示该初始值是否至少有一种合法操作。外层循环d从2到R实际上到R-L因为y - d要落在y ∈ [L,R]内所以d R-L不y最小是Lx y - d 1所以d L-1才能保证x1对于小的y。但对于大的yd可以更大比如y Rd是R的一个因子可能d比L大此时x R - d可能还是大于等于 1 的。所以d的范围是2 d R-1但为了枚举y的倍数需要y从max(L, 2*d)开始。这样循环的次数是sum_{d2}^{R} (R - max(L, 2*d)) / d差不多是R log R。内层循环令y从max(L, 2*d)开始向上取最近的d的倍数然后每次y d直到y R。对于每个y令x y - d标记vis[x] true。最后统计vis[1]到vis[R]中true的个数就是答案。等等这样会不会重复统计同一个x可能对应多个(d, y)但用布尔数组只会标记一次没问题。但这里有个严重问题对于同一个x可能存在多个d使得xd是d的倍数且落在区间内但我们只需要一次布尔数组完美解决。复杂度分析外层d从 2 到 R内层每个d大约循环(R - max(L, 2*d)) / d次。总和近似R * (1/2 1/3 ... 1/R)的量级即R log R。对于R 10^6大概10^6 * 14 1.4e7次操作完全没问题。这个复杂度比枚举每个数的因子更优秀代码也更简单。3.3 差分数组的另一种实现方式如果题目要求统计“初始值落在某个区间[A,B]的个数”我们可以把单点标记改为diff[x]最后做前缀和得到每个位置的覆盖次数再区间求和。但本题只需要统计总数所以直接布尔数组即可。不过为了严谨我提供一种使用差分数组思想的写法开一个diff数组大小为R2对每个合法的x执行diff[x]最后遍历1..R累加并计数大于 0 的个数。这和直接vis[x]true本质一样只是用差分数组展示了前缀和的技巧。如果扩展题目询问多个区间差分数组就可以复用。3.4 参考代码C#include bits/stdc.h using namespace std; int main() { int L, R; cin L R; vectorint vis(R 2, 0); // 用差分数组记录覆盖次数 for (int d 2; d R - 1; d) { // y 必须是 d 的倍数且 y Ly d (保证 x1) int start max(L, 2 * d); // 向上取到 d 的倍数 if (start % d ! 0) start d - (start % d); for (int y start; y R; y d) { int x y - d; if (x 1 x R) { vis[x]; // 标记初始值 x 可到达区间内 } } } int ans 0; // 前缀和还原其实这里是直接统计 0 的个数 for (int i 1; i R; i) { if (vis[i] 0) ans; } cout ans endl; return 0; }这段代码用vis记录每个x被标记的次数最后统计大于 0 的个数。注意d的上界为什么是R-1因为y R而x y - d 1所以d y - 1 R - 1。当d R - 1时y - d 0不可能有合法x。另外d从 2 开始因为因子要大于 1。还有一个细节当L很小时比如L1start max(1, 2*d) 2*d没有问题。当d很大时比如d R/22*d R内层循环不会执行因为start R。所以可以很自然地跳过。那这个枚举d会不会把“非质数因子”也算进去当然会而且必须算。例如d4时y是 4 的倍数x y-4显然 4 是x的因子因为x(k-1)*4。所以d本身是合数也能产生合法操作不能只枚举质数。下面验证一下正确性对于任意一个合法操作(x, d)其中d | x令y xd那么y是d的倍数且y ∈ [L,R]。在我们的枚举中当外层循环到d时内层会遍历到y于是标记x。所以所有合法情况都被覆盖。反过来任何一个被我们标记的x都对应一个d和y xd且y是d的倍数所以x y-d (k-1)d确实是d的倍数因此d是x的因子操作合法。完美。再看极端情况x本身是质数它的因子只有 1 和它自己大于 1 的因子就是x自身所以操作只能是y 2x。这时d xy 2x。我们的枚举中d xy取2x内层会标记x正确。x1呢大于 1 的因子不存在所以x1永远不是合法初始值。我们的枚举中要标记x1需要y - d 1即y d1且d | y也就是d | (d1)只有d1满足但d2所以不会被标记正确。3.5 参考代码PythonL, R map(int, input().split()) vis [0] * (R 2) for d in range(2, R): start max(L, 2 * d) if start % d ! 0: start d - (start % d) for y in range(start, R 1, d): x y - d if 1 x R: vis[x] 1 ans sum(1 for i in range(1, R 1) if vis[i] 0) print(ans)Python 版本需要注意性能R10^6时内层总共约10^7次循环Python 能过但可能有点慢建议用 PyPy。如果超时可以优化当d较大时start可能直接大于R可以提前 break不行因为后面的d更大会更没戏所以可以直接if start R: break因为随着d增大start max(L, 2*d)只会增大。可以加这个剪枝。for d in range(2, R): start max(L, 2 * d) if start R: break ...但要注意如果L很大比如L500000, R1000000当d600000时start max(500000, 1200000) 1200000 R直接 break。这没问题因为d继续增大2*d更大start只会更大所以可以安全 break。4. 踩坑记录与常见问题排查4.1 质因数分解时漏掉大于根号的因子虽然最终代码没用到显式分解但如果你尝试用“枚举因子判断”的方法容易在分解质因数时只循环到sqrt(n)却忘了最后处理剩余的大质数。这个问题在数论题里很经典比如n 2 * 999983循环到sqrt(n)附近时n还没被除尽最后n 1就需要把剩余因子加入。我见过很多人在这个细节上翻车导致答案偏小。4.2 内层循环的起点计算错误计算start时如果直接start max(L, d)而不是2*d会把x0的情况算进去。题目要求初始值应该是正整数x0不合法。比如yd时x0操作因子是它本身其实 0 的因子没有意义所以必须从2*d开始。但还有一种情况如果L小于2*d我们取2*d这没问题如果L大于2*d我们要取L向上对齐到d的倍数注意别忘了对齐操作。4.3 标记数组容量不足导致越界x的最大值是多少x y - d R - 2 R - 2当d2所以x最大R-2但我们开R2大小绰绰有余。不过如果L很小d2时x最小可能是2*2 - 2 2所以x的下界是 1 就不会有越界。为了安全起见在标记之前检查x 1 x R别省这个判断。4.4 对“因子”的理解错误题目里的“因子”是指大于 1 的因子包括合数。有的同学只枚举质因子导致漏掉很多情况。例如x12质因子有 2、3但因子还有 4、6、12这些也能作为操作增量。如果只考虑质因子会漏掉一些可达目标。所以在自己的实现里要么枚举所有因子要么用我们上述的倍数枚举法天然包含了所有因子。4.5 差分数组的前缀和还原时机如果用vis数组做单点累加最后统计时直接看vis[i] 0不需要前缀和。但如果你把vis当差分数组用比如vis[x]然后在某个地方vis[x1]--那必须最后做前缀和才能得到每个点的实际值。我见过有人把这两种用法搞混导致结果全错。这个题里单点加即可不需要区间加所以别硬套差分的写法。5. 举一反三这类题目的通用套路5.1 倍数枚举法与调和级数复杂度这道题的核心优化在于把“枚举因子”转换为“枚举倍数”。对于每个d我们不是去找哪些数含有因子d而是直接遍历d的倍数从而利用调和级数1 1/2 1/3 ... 1/n ≈ ln n将总复杂度控制在O(n log n)。这个思想在筛素数、求约数和、GCD 计数等很多题目中都很常见。比如统计 1 到 n 中每个数的约数个数就可以用倍数枚举for (int d 1; d n; d) for (int j d; j n; j d) cnt[j];这段代码复杂度是O(n log n)远优于对每个数试除的O(n sqrt(n))。记住这个模式很多题都能用。5.2 反向思维从目标数倒推初始值题目问“哪些初始值能到达区间内的某个目标”正常思路是枚举初始值找因子但是那样复杂度高。我们反过来枚举操作增量d然后通过y xd是d的倍数这一关系直接批量生成合法的x。这种“正难则反”的思维方式在算法竞赛里非常关键经常能把一道暴力题变成优雅的数论题。5.3 区间问题的常见处理本题最后统计的是“有多少个初始值”如果用布尔数组标记答案就是标记数量。如果题目改成“区间内有多少个初始值”我们可以对标记数组做前缀和然后O(1)回答询问。这就是差分的价值。虽然本题没有明确要求多次查询但掌握这个扩展思路遇到变体就不会慌。5.4 蓝桥杯国赛的难度定位“普及”的难度意味着这题不是纯模板题需要一点思维转换。但核心知识点都是基础质因数分解、差分数组、调和级数。如果你在赛场上能快速识别出“倍数的关系”这题很快就能拿下。如果卡住了不妨从数据范围入手百万级别直接提示你要用O(n log n)甚至O(n)的算法然后往筛法、倍数枚举上联想。6. 一点实战体会我自己第一次做这题时也掉进了“枚举所有因子”的坑里写了半天vectorint fac然后对每个数遍历结果超时。后来意识到可以直接枚举d和它的倍数代码量瞬间少了三分之二而且跑得飞快。所以我想说的是遇到区间、倍数、因子这类关键词优先考虑调和级数枚举而不是傻傻地分解每个数。还有一个小技巧在本地测试时可以写一个暴力对拍程序比如枚举 1 到 1000 以内的所有x和它的因子验证正解的答案是否一致。对拍真的能帮你快速发现边界条件比如x1是否计入、dy时x0是否排除等。我建议你在学习任何算法题时都养成对拍的习惯这比看十篇题解都管用。最后再分享一个细节vis数组不要用bool因为同一个x可能被多个d标记虽然我们只关心是否大于 0但用int计数在调试时能帮你发现是不是有多余的重复标记导致逻辑错误。如果发现某个x被标记了几十次你就要想想是不是枚举了不合法的d。实际提交时把int换成bool也完全没问题只是调试阶段用int更方便。