P6222

· · 题解

\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k\gcd(i,j)\mu^2(\gcd(i,j)) =\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k\gcd(i,j)\sum\limits_{d^2\mid i,d^2\mid j}\mu(d) =\sum\limits_{d=1}^n\mu(d)d^{2k+2}\sum\limits_{i=1}^{\lfloor\frac{n}{d^2}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d^2}\rfloor}(i+j)^k\gcd(i,j) =\sum\limits_{d=1}^n\mu(d)d^{2k+2}\sum\limits_{i=1}^{\lfloor\frac{n}{d^2}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d^2}\rfloor}(i+j)^k\sum\limits_{g\mid i,g\mid j}\varphi(g) =\sum\limits_{d^2g\leq n}\mu(d)d^{2k+2}\varphi(g)g^k\sum\limits_{i=1}^{\lfloor\frac{n}{d^2g}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d^2g}\rfloor}(i+j)^k

记 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) 的复杂度。