题解：P10322 高洁（Purity）
NaCly_Fish
·
·
题解
我们考虑有哪些数的能级至多为 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 所有不同质因子的乘积，可以直接使用之前的操作方法处理。