P3768 简单的数学题

· · 个人记录

P3768 简单的数学题

题意

给定 n 求：

\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)

正文

性质：

n=\sum_{d|n}\varphi(d)

那么：

\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)\\ =\sum_{i=1}^n\sum_{j=1}^nij\sum_{d|\gcd(i,j)}\varphi(d)\\ =\sum_{d=1}^n\varphi(d)\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]ij\\ =\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(id)(jd)\\ =\sum_{d=1}^n\varphi(d)d^2\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}ij\\ =\sum_{d=1}^n\varphi(d)d^2(\sum_{i=1}^{\lfloor\frac nd\rfloor}i)^2\\

考虑整除分块，之后就是如何求 \varphi(d)d^2 的前缀和。考虑杜教筛。

f*g=\sum_{d|x} f(d)\cdot g(\frac xd)\\ g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^ng(d)S(\lfloor\frac nd\rfloor)

那么设 g(i)=i^2，此时的 g 为完全积性函数，同时

(f*g)(x)\\ =\sum_{d|x}f(d)\cdot g(\frac xd)\\ =\sum_{d|x}\varphi(d)d^2\frac{x^2}{d^2}\\ =x^2\sum_{d|x}\varphi(d)\\ =x^3\\ S(n)=(\sum_{i=1}^n i^3)-\sum_{d=2}^nd^2S(\lfloor\frac nd\rfloor)

接下来就容易做了。