P4902 乘积 题解

发现最外层的累乘可以通过前缀积直接求出来，因此只需要求：

发现分子 $i$ 对答案影响不大，考虑将他们分开，得：

即：

考虑函数 $f(x)=\sum_{j=1}^x\lfloor \frac{x}{j} \rfloor$，发现 $f(x)=f(x-1)+\sum_{d|x}1$，而一个数的因数个数可以在 $O(n\log n)$ 的复杂度内求出，因此前半部分的复杂度即为 $O(n\log n)$。

现在的目标就是求出：

不妨假设函数 $g(x)=\prod_{j=1}^x j^{\lfloor \frac{x}{j} \rfloor}$，发现 $g(x)=g(x-1)\times\prod_{d|x}d$，将 $\prod_{d|x}d$ 前后两两配对，发现若 $x$ 为完全平方数，则 $\prod_{d|x}d=x^{\sum_{d|x \land d < \sqrt x}1} \sqrt x$，否则有 $\prod_{d|x}d=x^{\sum_{d|x \land d < \sqrt x}1}$，因此也可以在 $O(n\log n)$ 时间内求出。

最后将上面的所有东西相乘，做前缀积即可。