# 简单统计

## 解法与署名

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

出题人解法为整除分块和递增记忆化，完整说明见[整除分块](solution-alternative-quotient-blocks.zh.md)，程序为 [alternative-quotient-blocks.cpp](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` 包含十份输入的固定种子和目的。编译程序后，可运行：

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

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

## 实测结果

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

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

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