P6222

记 $f(x)=x^k\sum\limits_{d^2g=x}\mu(d)d^2\varphi(g)$，$g(x)=\sum\limits_{i=1}^x\sum\limits_{j=1}^x(i+j)^k$。

则 $ANS=\sum\limits_{k=1}^nf(k)g(\frac{n}{k})$，是标准的整除分块形式。

则只需要预处理出 $f$，$g$ 即可 $O(\sqrt n)$ 回答单次询问。

先线性筛出 $\mu(x)$，$\varphi(x)$，$x^k$。

注意到先暴力枚举 $d$，然后枚举 $g$ 来贡献 $f$ 的复杂度为 $O(\int_1^n\frac{n}{x^2}\ dx)=O(n)$，而 $g(x)=g(x-1)+2\sum\limits_{i=x+1}^{2x}i^k-(2x)^k$，故可以递推处理。

则总复杂度 $O(n+T\sqrt n)$。

另外地，注意到 $f$ 是积性函数，而所求即是 $\sum\limits_{ij\leq n}f(i)\Delta_g(j)$，其中 $\Delta_g(x)$ 是 $g(x)$ 的差分，应用积性函数狄利克雷卷积一般函数的技巧可以做到 $O(n\log\log n+T)$ 的复杂度。