简单统计¶

解法与署名¶

首选差分与倍数筛，程序为 std.cpp。Codex（GPT-6）对本题递推式作差，得到按真因子累加的递推，并应用倍数筛实现；倍数筛本身是已有技术。

出题人解法为整除分块和递增记忆化，完整说明见整除分块，程序为 alternative-quotient-blocks.cpp。该方案直接求递推式，允许流式读取查询。差分方案降低预处理的渐进时间，但当前实现需要存储查询。

对相邻参数作差¶

所有正参数计算均在模 \(P=998244353\) 意义下进行。令 \(F(0)=0\) ，定义

\[ D(n)=F(n)-F(n-1)\pmod P\qquad(n\ge1) \]

比较 \(F(n)\) 与 \(F(n-1)\) .对 \(i\ge2\) ，只有当 \(i\) 整除 \(n\) 时，\(\lfloor n/i\rfloor\) 才比 \(\lfloor(n-1)/i\rfloor\) 大一。新出现的 \(i=n\) 项也可这样处理，因为 \(F(0)=0\) .因此

\[ D(n)=1+\sum_{\substack{i\mid n\\i\ge2}}D(n/i)=1+\sum_{\substack{d\mid n\\d<n}}D(d)\pmod P \]

特别地，\(D(1)=1\) .这个等式只用非负参数；负参数直接按题意返回，不参与筛法。

按倍数更新¶

令 \(N\) 为所有正查询的最大值；没有正查询时令 \(N=0\) .初始化每个 \(D(n)\) 为 \(1\) .依次处理 \(d=1,\ldots,N\) ，把已经确定的 \(D(d)\) 加到 \(D(2d),D(3d),\ldots\) 中。用前缀和恢复答案：

\[ F(n)=\sum_{d=1}^{n}D(d)\pmod P \]

每次加法立即取模。两项之和小于 \(2P\) ，可用有符号 32 位整数；若改成延后取模，须重新分析中间值。

正确性¶

处理 \(d\) 前，它的全部真因子都小于它，且每个真因子的贡献已经恰好加入一次。因此此时保存的 \(D(d)\) 等于差分递推的值。按 \(d\) 归纳，所有差分都正确。前缀和由定义望远镜相消，得到全部 \(F(n)\) .对非正参数直接返回参数，覆盖所有查询。

复杂度与取舍¶

倍数更新次数为 \(\sum_{d=1}^{N}(\lfloor N/d\rfloor-1)\) .总时间 \(O(N\log(N+1)+Q+1)\) ，当前实现的空间为 \(O(N+Q+1)\) .整除分块为 \(O(N\sqrt{N}+Q+1)\) 时间、\(O(N+1)\) 空间。

差分方案作为标程是因为预处理时间阶更低；整除分块是时间与空间取舍不同的并列方案，不需要提前保存查询。两者的实测结果与当前时限适用性见文末。

验证与运行¶

直接按定义枚举所有分母，对拍空查询、负数、重复查询及递增和递减查询；全范围另与整除分块逐项比较。

每题的 tests/plan.json 包含十份输入的固定种子和目的。编译程序后，可运行：

python tests/generate.py --out-dir <output-directory> --std <compiled-program>

省略 --std 只生成输入，--case 01 选择单份输入。独立验证脚本见 check_r15.py。五轮交替计时与内存记录见测量数据，环境说明见评测环境与性能。有限测试与具体程序的计时不代替上面的证明，也不保证所有同阶实现都能在同一时限内通过。

实测结果¶

程序	最慢用例中位时间	峰值工作集
标程	0.044081 秒	6.46 MiB
补充程序	0.322212 秒	6.01 MiB

参考时限为 0.5 秒。十份已测正式输入上，两份程序结果一致，均在该时限内完成。上述内存是包含进程开销的峰值工作集，时间与内存的最大值可能来自不同输入。

整除分块的渐进时间更高，但当前范围和校准时限不能可靠排除它；没有扩大范围或缩短正常通过余量来人为区分。