题解：某不科学的单调序列的最大公约数之和¶

Codex（GPT-6）：应用欧拉函数展开和可重复组合计数，结合整除分块及前缀递推，给出本题证明与实现。

公约数展开与多重集合¶

由 \(g=\sum_{d\mid g}\varphi(d)\) ，只需统计所有元素被 \(d\) 整除的序列。除以 \(d\) 后，元素属于 \(1,\ldots,q\) ，其中 \(q=\lfloor n/d\rfloor\) .一个不增序列唯一对应一个大小为 \(m\) 的多重集合，方案数为隔板法给出的 \(\binom{q+m-1}{m}\) .因此

\[ A=\sum_{d=1}^{n}\varphi(d)\binom{\lfloor n/d\rfloor+m-1}{m} \]

每个序列对全部公约数贡献的欧拉函数之和等于其最大公约数，故该式准确计数答案。

按商分块¶

设 \(\Phi(x)=\sum_{d\le x}\varphi(d)\) .在相同商 \(q\) 的区间 \([l,r]\) ，贡献为

\[ \left[\Phi(r)-\Phi(l-1)\right]\binom{q+m-1}{m},\qquad r=\lfloor n/q\rfloor \]

用线性筛预处理到 \(B=\min(n,2000000)\) .由 \(\sum_{d\mid u}\varphi(d)=u\) ，有

\[ \Phi(x)=\frac{x(x+1)}2-\sum_{k=2}^{x}\Phi(\lfloor x/k\rfloor) \]

右侧继续按商分块并记忆化大参数。递归参数严格减小，小值来自筛法，因而递推正确。所有大参数均为 \(\lfloor n/i\rfloor\) ，用 \(\lfloor n/x\rfloor\) 作为缓存下标，存储 \(O(n/B)\) 项。

共享组件也维护 \(\sum_{d\le x}d\varphi(d)\) ；本题只使用第一分量，第二分量不参与答案，也不改变渐进复杂度。

组合数求值¶

令 \(C(q)=\binom{q+m-1}{m}\) .从 \(C(1)=1\) 开始，利用

\[ C(q)=C(q-1)\frac{q+m-1}{q-1} \]

线性预处理到 \(B\) .\(q-1<P\) ，其逆元存在，可使用线性逆元递推。较大的商直接计算

\[ C(q)=\frac{q(q+1)\cdots(q+m-1)}{m!} \]

这样的商至多 \(n/B\) 个，每个耗时 \(O(m)\) .注意 \(q+m-1\) 可能达到或超过 \(P\) ：分子中含 \(P\) 时结果为零。因为 \(m<P\) ，分母始终可逆。不要采用会对零阶乘求逆的普通阶乘表商式。

正确性与复杂度¶

隔板法计数每个合法序列一次；欧拉函数展开恢复其最大公约数；分块和前缀递推精确求得每段系数。故所有段的模和就是答案。

阈值为 \(B\) 时，预处理为 \(O(B+m)\) ，大前缀求和为 \(O(n/\sqrt B)\) ，大商组合数为 \(O(nm/B)\) .合计 \(O(B+n/\sqrt B+nm/B)\) 时间、\(O(B+n/B)\) 空间。二分快速幂仅用于一个逆阶乘，代价 \(O(\log P)\) ；这里 \(P\) 固定。全部乘法使用 64 位中间值并分步取模。

直接对所有 \(d\) 求和可以核验中等规模，但需要 \(O(n)\) 存储或更多在线运算，不适合完整范围。连续点插值也能计算组合数多项式，但同样需要 \(O(m)\) 单次求值及额外数组，本题直接乘积更简单。

见标准程序、前缀组件、测试说明及性能记录。