P4902 乘积 题解

· · 题解

思路

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

\prod_{j=1}^i (\frac{i}{j})^{\lfloor \frac{i}{j} \rfloor}

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

\prod_{j=1}^i i^{\lfloor \frac{i}{j} \rfloor}(\prod_{j=1}^i j^{\lfloor \frac{i}{j} \rfloor})^{-1}

即：

i^{\sum_{j=1}^i\lfloor \frac{i}{j} \rfloor}(\prod_{j=1}^i j^{\lfloor \frac{i}{j} \rfloor})^{-1}

考虑函数 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)。

现在的目标就是求出：

\prod_{j=1}^i j^{\lfloor \frac{i}{j} \rfloor}

不妨假设函数 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) 时间内求出。

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

code