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

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)$ 单次求值及额外数组，本题直接乘积更简单。

见[标准程序](std.cpp)、[前缀组件](totient-sums.hpp)、[测试说明](tests/README.md)及[性能记录](../../../docs/benchmark-R36.json)。