题解：P9060 [Ynoi2002] Goedel Machine

简单数据结构题。认为 $n,m$ 同阶。

对每个素数计算答案后合并。首先，每个数只有至多一个 $> \sqrt V$ 的素因子，因此我们分开做 $\le \sqrt V$ 的素因子和 $> \sqrt V$ 的素因子。

记区间 $[l,r]$ 中有 $k$ 个数是 $p$ 的倍数，会贡献 $p^{2^k-1}$。对于每个 $1 \le k \le cnt_p$（$cnt_p$ 表示全局中多少个数为 $p$ 的倍数），预处理 $p^{2^k}$ 及其逆元。

这样很容易使用莫队做到 $O(n \sqrt n)$。

考虑计算 $[l,r]$ 中 $p$ 的幂次。设区间中分别有 $c_i$ 个数满足 $\nu_p(a) = i$（$i \le \log_p(V) = t$），则答案显然是：

因此我们需要维护 $t$ 个序列前缀和。复杂度为 $O(n \sum_{p \le \sqrt V} \log_p(V))$。注意到，这样的 $p$ 大概是 $O(\frac{\sqrt{V}}{\ln V})$ 个，因此 $\sum_{p \le \sqrt V} \log_p(V) \approx O(\sqrt V)$。

注意此处需要使用光速幂防止复杂度退化（维护 $p^{2^k}$ 也行）。

综上所述，我们在 $O(n \sqrt n + n \sqrt V)$ 的复杂度内解决了此题。