.

wind_boy · 2025-06-24 15:05:05 · 个人记录

题意：给定 n,a_{1\sim n}，求 \prod_{i=1}^n i^{a_i}.

从大到小枚举 i，设 i 的最小质因子为 b_i，把 i^{a_i} 拆成 b_i^{a_i}\cdot (i/b_i)^{a_i}，这样就可以使得只有质数处 a_p\neq 0. 做 O(\dfrac n{\ln n}) 次快速幂即可. 复杂度 O(n\dfrac{\log mod}{\log n}).