P10322 高洁（Purity）
设 \(d=\prod p_i^{c_i}\)，容易发现当 \(d\mid i^k\) 时，\(i^k\) 的所有质因子的幂次都不小于 \(d\) 的所有所有质因子的幂次，即 \(i^k\) 含有的质因子的幂次至少为 \(\lceil c_i/k\rceil\)，因此我们设
\[f_k(d)=\prod p_i^{\lceil c_i/k\rceil}
\]
那么就有 \(d\mid i^k\Leftrightarrow f_k(d)\mid i\)，因此能级为 \(k\,(k>1)\) 的答案为
\[\begin{aligned}ans(k)&=\sum\limits_{i=1}^n i^{k+1} [f_k(d)\mid i][f_{k-1}(d)\not\mid i]\\ &=f_k(d)^{k+1}\sum\limits_{i=1}^{\lfloor n/f_k(d)\rfloor}i^{k+1}[(f_{k-1}(d)/f_k(d))\not\mid i] \end{aligned}
\]
设 \(m=\lfloor n/f_k(d)\rfloor\)，\(q_k=f_{k-1}(d)/f_k(d)\)，则
\[\begin{aligned}ans(k)&=f_k(d)^{k+1}\sum\limits_{i=1}^mi^{k+1}(1-[q\mid i])\\&=f_k(d)^{k-1}\sum\limits_{i=1}^mi^{k+1}-q_k^{k+1}\sum\limits_{i=1}^{\lfloor m/q_k\rfloor}i^{k+1} \end{aligned}
\]
\(k=1\) 时答案也很简单，
\[ans(1)=\sum\limits_{i=1}^n {i^2 [d\mid i] }=d^2\sum\limits_{i=1}^{\lfloor n/d\rfloor}i^{2}
\]
整个题就变成了自然数的 \(k\) 次幂和的问题：
\[s_k(n)=\sum\limits_{i=1}^n{i^k}$$可以直接 $\mathcal{O}(k^2)$ 递推求出。最后还需要求出能级为 $0$ 的数的和，记 $ord=\prod p_i$，这就是$$\sum\limits_{i=1}^ni[ord\not\mid i]\]
用上文办法处理即可。
时间复杂度 \(\mathcal{O}(Tk^2(k+\log n))\)。
