题面

现有 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，并且有 $m$ 次查询。每次查询时需对给定的 $p$ 计算下面表达式的值：

$$\sum\limits_{1 \le i \le n}\Bigl\lfloor \frac{a_i}{\lceil\log_{p}a_i\rceil}\Bigr\rfloor$$

数据范围：

$1 \le n, m \le 5 \times 10^5$

$2 \le a_i, p_i \le 10^9$

题目链接

分析

我们注意到，$\lceil\log_{p}a_i\rceil$ 的取值在题目的取值范围下其实非常有限：

$$\lceil\log_{p}a_i\rceil \in [1, 31]$$

也就是说，对于同一个 $p$ ，$\lceil\log_{p}a_i\rceil$ 的值很可能对于多个 $a_i$ 是相等的。

另外我们注意到 $\log_{p}a_i$ 是单调递增的。如果我们先对这 $n$ 个整数从小到大排序，那么对于排序后的数列，我们可以将其划分为若干个连续区间，使得每个区间内 $\lceil\log_{p}a_i\rceil$ 的值都相等。那么我们不妨将排序后的数组连续地划分成 $31$ 个区间（区间可以包含 $0$ 个元素），使得每个区间内所有 $a_i$ 的 $\lceil\log_{p}a_i\rceil$ 都相等。如果我们能够快速地求出每个区间的区间和加起来，这样复杂度就能降低不少。

既然 $\lceil\log_{p}a_i\rceil$ 的取值情况很少，我们可以考虑预处理所有的 $\frac{a_i}{k} \ (k \in \mathbb{Z}, k \in [1, 31])$ 。同时在预处理的时候，我们可以将其处理为前缀和的形式，这样我们就可以以 $\mathcal{O}(1)$ 的复杂度求出上面提到的每个区间的区间和。

至于区间具体如何划分，我们不妨借助二分查找。第 $k$ 个区间的第一个元素也就是原数组中第一个大于 $p^k$ 的元素。

这样一来，预处理的复杂度为 $\mathcal{O}(n)$ ，$m$ 次查询的复杂度为 $\mathcal{O}(m\log{n})$ ，而常数则为 $31$ 。

实现

完整参考代码