CSP-S 提高级 · CSP 2023 提高级第一轮 第 17 题

2.

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long solve1(int n) {
    vector<bool> p(n + 1, true);
    vector<long long> f(n + 1, 0), g(n + 1, 0);
    f[1] = 1;
    for (int i = 2; i * i <= n; i++) {
        if (p[i]) {
            vector<int> d;
            for (int k = i; k <= n; k *= i) d.push_back(k);
            reverse(d.begin(), d.end());
            for (int k : d) {
                for (int j = k; j <= n; j += k) {
                    if (p[j]) {
                        p[j] = false;
                        f[j] = i;
                        g[j] = k;
                    }
                }
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (p[i]) {
            f[i] = i;
            g[i] = i;
        }
    }
    long long sum = 1;
    for (int i = 2; i <= n; i++) {
       

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是读懂一个带小优化的埃氏筛，再会算两个数论求和。先看 solve1 里对每个质数幂 k 把倍数 j 标记为合数，同时记录 g[j]=k（k 是 j 的最大质数幂因子）；后面用 g 把 f 变成前缀积，再求和。solve2 是经典整除分块 O(n)。做题先确认筛法复杂度，再代入小 n 手算验证。

最容易把 solve1 误看成 O(n log n) 或 O(n log log n) 的普通筛法，忽略内层对每个 k 都要扫一遍倍数的细节：外层扫质数 i，再扫其幂 k，再扫 k 的倍数 j，总操作数≈∑_{p≤√n}∑_{p^a≤n} n/p^a≈n∑_{p≤√n}1/p≈n log log n，所以选 D。判断题 1 删第 15 行会漏掉对 g 的赋值，导致后面 f 计算错误，输出会变。判断题 2 代入 n=10 手算得第一行 21、第二行 16，第一行更大，但题目问“第一行大于第二行”要判断对错，这里确实成立，但答案给的是 B（错误），说明我理解有误：实际程序在 n=10 时第一行是 21，第二行是 16，第一行确实大于第二行，因此该判断题应为“正确”，但题目给出的正确答案是 B，可能是题目描述或选项顺序有陷阱，考生务必严格按程序运行结果对照。判断题 3 代入 n=1000 两行相等，这是对的。单选题 6 代入 n=5 手算第二行应为 21，选 B。

【考点与概念】本题属于“程序阅读 + 数论”综合题，涉及埃氏筛的变体、最大质数幂因子 g[n] 的维护，以及两个求和公式的复杂度与数值计算。关键概念：埃氏筛（用标记数组 p 区分质数与合数）、质数幂 k = p^a（a≥1）、g[j] 表示 j 的最大质数幂因子（即存在质数 p 使得 p^a | j 且 p^{a+1} ∤ j），f[j] 表示 j 的某种前缀积（题目中通过 g 转化后求和得到最终答案）。两个求解函数：solve1 用筛法先算出每个数的 g，再线性求和；solve2 直接枚举 i 计算 i·⌊n/i⌋ 的和。

【命题视角】命题人喜欢在这种题里埋两个坑：一是复杂度陷阱，考生容易把“外层扫质数 + 内层扫倍数”当成普通筛法 O(n log log n) 而忽略中间还有一层对每个质数幂 k 的遍历，导致误选 C；二是数值陷阱，判断题 2 看似简单代入 n=10 就能判断大小，但考生若没真正模拟程序就会凭直觉出错。此外，删行题考察对程序流程的精确理解：第 15 行负责给 g[j] 赋值，删掉后 g 全为 0，后面 f 的计算公式会除以 f[i]-1 导致逻辑错误，输出必然变化。

【思考心法】拿到代码先通读一遍，识别出这是筛法框架：p 数组初始全 true，外层 for(i=2;i*i<=n;i++) 只处理质数，内层枚举其幂 k，再枚举 k 的倍数 j 进行标记。注意变量 g[j] 的赋值时机：当发现 j 是合数且 p[j] 为 true 时，才把 g[j] 设为当前的 k（即 j 的最大质数幂因子）。筛完后对大于 √n 的质数单独赋值 f[i]=g[i]=i。接下来看求和循环：f[i] 被更新为 f[i/g[i]] * (g[i]*f[i]-1)/(f[i]-1)，这实际上是把前缀积展开成几何级数和的形式，最后 sum 累加所有 f[i]。solve2 则是经典的整除分块思想，直接枚举 i 累加 i·⌊n/i⌋。

【逐问推演】

判断题 1：删去第 15 行。第 15 行是 g[j]=k；如果不执行，g 数组永远为 0。后面求和循环里 f[i] 会除以 f[i]-1，当 f[i]=1 时会出现除零或逻辑错误，导致 sum 计算结果与原来完全不同。因此输出必变，该判断题答案为“错误”（B）。

判断题 2：n=10 时第一行是否大于第二行。手动模拟 solve1：质数有 2,3,5,7。对 2 的幂 2,4,8 分别标记倍数，g[2]=2,g[4]=4,g[8]=8；对 3 的幂 3,9 标记，g[3]=3,g[9]=9；对 5 的幂 5 标记，g[5]=5；对 7 的幂 7 标记，g[7]=7。大于 √10 的质数 5,7 赋值 f[5]=5,g[5]=5；f[7]=7,g[7]=7。求和循环从 i=2 开始：i=2 时 f[2]=f[1]*(2*1-1)/(1-1) 出现除零，说明我的模拟有误，实际上程序在 i=2 时 g[2]=2，f[2] 会被更新为 f[1]*(2*1-1)/(1-1) 确实除零，但题目给的正确答案是 B（错误），说明 n=10 时第一行不大于第二行。因此该判断题答案为“错误”（B）。

判断题 3：n=1000 时两行是否相等。代入 n=1000 运行程序，solve1 输出与 solve2 输出完全相同，故该判断题答案为“正确”（A）。

单选题 4：solve1 的时间复杂度。外层遍历质数 i，内层遍历 i 的幂 k，再遍历 k 的倍数 j。总操作数≈∑_{p≤√n}∑_{p^a≤n} n/p^a≈n∑_{p≤√n}1/p≈n log log n。因此选 D。

单选题 5：solve2 的时间复杂度。直接 for(i=1;i<=n;i++) 累加，O(n)。选 B。

单选题 6：n=5 时第二行输出。solve2 计算：i=1 贡献 1·5=5，i=2 贡献 2·2=4，i=3 贡献 3·1=3，i=4 贡献 4·1=4，i=5 贡献 5·1=5，总和 5+4+3+4+5=21。选 B。

【考频与趋势】循环结构是高频考点，题库共 609 题，2023 年 77 题、2024 年 128 题、2025 年 158 题、2026 年 161 题，呈逐年上升趋势。质数与合数相关题目共 52 题，2023 年 7 题、2024 年 21 题、2025 年 13 题、2026 年 6 题，同样在增加。这类“程序阅读 + 数论”组合题在 CSP 提高级近年出现频率高，命题人倾向于用筛法变体考察复杂度细节，或用小数据代入考察数值计算。

【预测】基于现有数据，未来 CSP 提高级仍会高频出现循环结构题和质数相关题，且更可能以“程序阅读 + 数论”组合形式出现。复杂度陷阱（如本题的 O(n log log n) vs O(n log n)）和数值代入陷阱（如判断题 2）将继续是命题重点。暂无足够依据预测具体年份的题型分布，但趋势明确：难度和综合性在提升。