题解 P6788 【「EZEC-3」四月樱花】
Aleph1022
·
·
题解
首先有引理：n^{\sigma_0(n)} = \prod_{d|n} d^2。
证明：
\begin{aligned}n^{\sigma_0(n)} & = \prod_{d|n} n \\ & = \prod_{d|n} d \cdot \frac nd \\ & = \left(\prod_{d|n} d\right) \left(\prod_{d|n} \frac nd\right) \\ & = \left(\prod\limits_{d|n} d\right)^2 \\ & = \prod\limits_{d|n} d^2\end{aligned}
然后这道题就变成了
\begin{aligned}s&=\prod\limits_{i=1}^t \prod\limits_{d|i} \frac{\prod_{k|d} k^2}{\prod_{k|d} (k+1)^2} \\&=\prod\limits_{i=1}^t \prod\limits_{d|i} \prod\limits_{k|d} \frac{k^2}{(k+1)^2} \\&=\prod\limits_{k=1}^t \left[\frac{k^2}{(k+1)^2}\right]^{\sum_{d=1}^{\left\lfloor t/k\right\rfloor} \left\lfloor\frac t{dk}\right\rfloor}\end{aligned}
不难发现指数的东西可以数论分块计算，数论分块嵌套就得到了一个 O(n^{3/4}) 的解法。
实际上，指数上的东西等于
\sum\limits_{d=1}^{\left\lfloor\frac tk\right\rfloor} \sigma_0(d)
这个东西可以线性筛预处理 n^{2/3} 以内的前缀和，以上的使用数论分块计算即可。
此处总复杂度为 O(n^{2/3})。
另外需要计算 \prod\limits_{k=l}^r \frac{k^2}{(k+1)^2}，不过不难发现这个就是 \frac{l^2}{(r+1)^2}。