本题的定位不是难题，旨在帮助选手追忆基本的计数技巧，虽然正赛已有多年没考如此传统的计数，但适当练练还是有用的。

本题的出题灵感来自下面这个广为人知的式子：

$$\sum_{i=1}^n \mu^2(i) = \sum_{i=1}^n \mu(i) \lfloor \dfrac{n}{i^2} \rfloor $$

其中，等式左边的意义是计算 $1 \sim n$ 中无大于 $1$ 的平方因子的数的个数，而右边则是考虑对每个数的平方因子进行容斥，枚举每个数的某一个平方因子 $i$，统计所有 $i^2$ 的倍数，再带个 $\mu(i)$ 的容斥系数。容易发现，对于一个数 $x$，满足 $v(x) = \prod_{j = 1}^t p_j^{\alpha_j}$，则右式

会将其统计 $\sum_{j = 0}^t (-1)^j \binom{t}{j} = 0^t = [t = 0]$ 次，正好符合左式的计数意义。

很容易将其推广到特殊性质 B，注意到性质 B 实际上就是算 $\sum_{i=1}^n \mu^2(i) i^k$

则上式 $=\sum_{i=1}^n \mu(i) \sum_{i^2 | x} x^k = \sum_{i=1}^n \mu(i)i^{2k}S(\lfloor \dfrac{n}{i^2} \rfloor)$

其中 $S(n) = 1^k + 2^k + \dots + n^k$ 为自然数等幂和。

那么对于一般情况呢？注意到上面的容斥其实只是莫比乌斯反演的特殊情形，我们完全可以利用 Dirichlet 积与反演工具，手动构造容斥系数。

具体地，我们构造一个序列 $b_i$ 使得 $a_n = \sum_{d | n} b_d$。

则

$$\begin{aligned}\sum_{i = 1}^n a_{v(i)}i^k &= \sum_{i = 1}^n \sum_{d | v(i)} b_d i^k \\&= \sum_{i=1}^n\sum_{d^2 | i} b_di^k \\&= \sum_{d = 1}^{\lfloor \sqrt n \rfloor}b_dd^{2k}S(\lfloor \dfrac{n}{d^2} \rfloor) \end{aligned} $$

上面利用到了 $d | v(i) \Leftrightarrow d^2 | i$ 的数论事实，将 $i$ 作质因数分解即可证明。

那如何得到这个序列 $b$？注意到 $a = b \circ 1$，那么 $b = a \circ \mu$（$\circ$ 为 Dirichlet 卷积），可以在 $O(m \log m)$ 或 $O(m \log \log m)$ 的时间内得到序列 $b$。

现在问题归结为如何对 $d \le \sqrt n$ 算 $S(\lfloor \dfrac{n}{d^2} \rfloor)$。

我们知道，利用拉格朗日插值，单个 $S(n)$ 容易在 $O(k)$ 时间算出，但我们没必要对每个 $d$ 都这么算，可以在 $\dfrac{n}{d^2}$ 较小时直接预处理 $S$。 标程中选择在 $\dfrac{n}{d^2} \le n^{2/3}$ 时预处理 $S$，这样只需要对 $O(n^{1/6})$ 个 $d$ 进行拉格朗日插值，总时间复杂度 $O(m \log m + n^{2/3} + kn^{1/6})$，可以通过本题。（注意使用线性筛来做到 $O(n^{2/3} \dfrac{\ln k}{\ln n})$ 预处理 $S$，不要直接使用快速幂）

注：本题还有一种化式子的方法，可以得到一种更复杂的做法：

$\sum_{i=1}^n a_{v(i)}i^k = \sum_{d = 1}^{\lfloor \sqrt n \rfloor} a_dd^{2k} \sum_{i=1}^{\lfloor \frac{n}{d^2} \rfloor} \mu^2(i)i^k$

令 $f(x) = \mu^2(x)x^k$，显然其是积性函数，且满足用 min_25 筛求前缀和的条件，故可以用 min_25 筛算出 $\sum_{i=1}^{\lfloor \frac{n}{d^2} \rfloor} \mu^2(i)i^k$

但 min_25 筛要求对每个 $i$ 算出 $S(\lfloor \dfrac{n}{i} \rfloor)$，且筛法本身复杂度为 $O(\dfrac{n^{3/4}}{\ln n})$ ，导致总体时间复杂度稍劣。