题解

思路

由于因数对有序且求和对称，递推式可化为

$$f_{r+1}(n)=\sum_{d\mid n}f_r(d).$$

这是与常数函数 $1$ 的 Dirichlet 卷积。

做法

$f_0$ 为积性函数，且 $f_0(p^e)=2 (e\ge1)$。与 $1$ 重复做 $r$ 次 Dirichlet 卷积后仍为积性函数。对单个质数幂，生成函数为

$$\frac{1+x}{1-x}\cdot\frac1{(1-x)^r} =\frac{1+x}{(1-x)^{r+1}}.$$

所以

$$f_r(p^e)=\binom{r+e}{e}+\binom{r+e-1}{e-1}.$$

若 $n=\prod p_i^{e_i}$，答案就是各个上式的乘积。

子任务 1 直接按定义枚举因数递归。子任务 2 对每个质因子指数维护数组，用前缀和执行 $r$ 次因数卷积。满分算法预处理最小质因子和阶乘、逆阶乘，直接计算组合数。

复杂度

预处理为 $O(10^6\log\log10^6)$，每个询问按质因子个数计算，总空间复杂度为 $O(10^6)$。