题解 P6156 【简单题】

$$ ans=\sum_{i=1}^n\sum_{j=1}^n(i+j)^kf(gcd(i,j))gcd(i,j) $$ $$ \begin{aligned} ans & =\sum_{i=1}^n\sum_{j=1}^n(i+j)^kf(gcd(i,j))gcd(i,j) \\ & =\sum_{t=1}^nf(t)t^{k+1}\sum_{i=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}(i+j)^k[gcd(i,j)=1] \\ & =\sum_{t=1}^nf(t)t^{k+1}\sum_{i=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}(i+j)^k\sum_{d|gcd(i,j)}\mu(d) \\ & =\sum_{t=1}^nf(t)t^{k+1}\sum_{d=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\mu(d)d^k\sum_{i=1}^{\left\lfloor\dfrac{n}{dt}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{n}{dt}\right\rfloor}(i+j)^k \end{aligned} $$ 我们现在设 $$ sum(D)=\sum_{i=1}^{D}\sum_{j=1}^D(i+j)^k $$ 所以 $$ \begin{aligned} ans & =\sum_{t=1}^nf(t)t^{k+1}\sum_{d=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\mu(d)sum(\left\lfloor\dfrac{n}{dt}\right\rfloor) \\ & =\sum_{D=1}^nsum(\left\lfloor\dfrac{n}{D}\right\rfloor)\sum_{t|D}f(t)t^{k+1}\mu(\frac{D}{t})(\frac{D}{t})^k \\ & =\sum_{D=1}^nsum(\left\lfloor\dfrac{n}{D}\right\rfloor)D^k\sum_{t|D}f(t)t\mu(\frac{D}{t}) \end{aligned} $$ 我们又设 $$ g(D)=\sum_{t|D}f(t)t\mu(\frac{D}{t}) $$ 易知,g为积性函数 所以 $$ ans=\sum_{D=1}^nsum(\left\lfloor\dfrac{n}{D}\right\rfloor)D^kg(D) $$ 啊，这 我们先来考虑sum该怎么求 $$ \begin{aligned} sum(n) & =\sum_{i=1}^n\sum_{j=1}^n(i+j)^k \\ & =\sum_{d=2}^{2\cdot n}d^k\times \left\lfloor\dfrac{d}{2}\right\rfloor\times 2 \end{aligned} $$ 这个可以递推？ -------------------- 然后我们看g $$ g(n)=\sum_{t|n}f(t)t\mu(\frac{n}{t}) $$ 线筛