简单统计：整除分块¶

出题人解法；Codex（GPT-6）整理实现、边界与说明。程序：alternative-quotient-blocks.cpp。首选方案及比较见主解。

思路与正确性¶

初始保存 \(F(0)=0,F(1)=1\) .读到正查询 \(x\) 时，按递增顺序补齐尚未计算的值。计算 \(F(n)\) 所需的 \(F(\lfloor n/i\rfloor)\) 均满足 \(\lfloor n/i\rfloor<n\) ，所以已经可用。

若当前分母从 \(l\ge2\) 开始，设

\[ q=\lfloor n/l\rfloor,\qquad r=\lfloor n/q\rfloor \]

则 \([l,r]\) 内的分母具有同一商 \(q\) ，这一整段贡献 \((r-l+1)F(q)\) .累加后令 \(l=r+1\) ，直到超出 \(n\) .区间连续、不重不漏，恰好计算定义中的所有求和项；再对参数递增归纳，即得正确性。

复杂度与实现¶

商的不同取值有 \(O(\sqrt n)\) 个：分母不超过 \(\sqrt n\) 的部分至多有 \(\sqrt n\) 项，其余商不超过 \(\sqrt n\) .设最大正查询为 \(N\) ，总时间 \(O(N\sqrt N+Q+1)\) ，空间 \(O(N+1)\) .无正查询时仅处理输入输出。

乘积使用 64 位整数，每块立即取模。负数和零直接返回；重复或递减查询直接查表。该方案适合需要流式读取查询的场景，代价是更高的预处理时间阶。当前时限适用性见主解的测量。