题解 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})

线筛