题解：P9060 [Ynoi2002] Goedel Machine
Purslane
·
·
题解
简单数据结构题。认为 n,m 同阶。
对每个素数计算答案后合并。首先，每个数只有至多一个 > \sqrt V 的素因子，因此我们分开做 \le \sqrt V 的素因子和 > \sqrt V 的素因子。
- 素因子 p > \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)。
- 素因子 p \le \sqrt V。
考虑计算 [l,r] 中 p 的幂次。设区间中分别有 c_i 个数满足 \nu_p(a) = i（i \le \log_p(V) = t），则答案显然是：
\sum_{i=1}^t i(2^{\sum_{j \ge i} c_j} - 2^{\sum_{j > i} c_j})
因此我们需要维护 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) 的复杂度内解决了此题。