自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:56:54，当前版本为作者最后更新于2024-04-05 22:42:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我们考虑有哪些数的能级至多为 $k$ —— 即满足 $d \mid i^k$。可以将 $d$ 进行质因数分解：

$$d=\prod_{j=1}^m p_j^{t_j}$$

然后考虑到 $d \mid i^k$ 等价于 $i^k$ 的所有质因子的幂次都不小于 $d$ 对应质因子的幂次。即 $i$ 含有质因子 $p_j$ 的数量至少为 $\lceil t_j/k \rceil$。现在可以设

$$f_k(d)=\prod_{j=1}^rp_j^{\lceil t_j/k\rceil}$$

这样就得到了结果：$d \mid i^k \Leftrightarrow f_k(d) \mid i$。然后就能得到能级为 $k \ (k > 1)$ 的所有数的答案之和：

$$\sum_{i=1}^ni^{k+1}[f_k(d) \mid i][f_{k-1}(d)\nmid i] $$$$=f_k(d)^{k+1}\sum_{i=1}^{\lfloor n/f_k(d)\rfloor}i^{k+1}[\left(f_{k-1}(d)/f_k(d)\right) \nmid i] $$

而对于 $k=1$ 的情况，条件就只是 $d \mid i$，答案也很简单：

$$\sum_{i=1}^ni^2 [d \mid i]=d^2 \sum_{i=1}^{\lfloor n/d \rfloor}i^2 $$

设 $q_k=f_{k-1}(d)/f_k(d)$，上面这个问题可以转化为（$m=\lfloor n/f_k(d) \rfloor$）：

$$\sum_{i=1}^mi^{k+1}(1-[q_k \mid i])=\sum_{i=1}^mi^{k+1}-q_k^{k+1}\sum_{i=1}^{\lfloor m/q_k \rfloor}i^{k+1} $$

整个问题就变成了简单的自然数 $k$ 次幂和：

$$S_k(n)=\sum_{i=1}^ni^k$$

这个东西有很多种算法，比如有：

$$S_k(n)=\sum_{i=0}^{n-1}(i+1)^k=\sum_{j=0}^k\binom kj (S_j(n)-n^j+0^j) $$

就可以简单地递推计算。

注意到 $k$ 不小于 $d$ 的质因子的最大幂次（即 $\max\{ t_1,\cdots,t_r \}$）时 $f_k(d)$ 全部都相同，这样就得到了能级的上限。可以发现 $k$ 很小（不超过 $27$），使用 $\Theta(k^2)$ 的递推法计算也可以通过。

最后还需要求出能级为 $0$ 的所有数之和，这样好办。它就是

$$\sum_{i=1}^n i [\text{ord}(d) \nmid i]$$

其中 $\text{ord}(d)$ 表示 $d$ 所有不同质因子的乘积，可以直接使用之前的操作方法处理。

---