P3768 Solution

link

\(\begin{aligned} \sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j) &=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nijd[\gcd(i,j)=d]\\ &=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij[\gcd(i,j)=1]\\ &=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij\sum_{k|i}\sum_{k|j}\mu(k)\\ &=\sum_{d=1}^nd^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}j\\ &=\sum_{s=1}^ns^2\sum_{d|s}d\mu(\frac{s}{d})\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}j\\ &=\sum_{s=1}^ns^2\varphi(s)\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}j \end{aligned}\)

\(\displaystyle f(x)=x^2\varphi(x)\)

构造 \(g(x)=x^2\),则 \(\displaystyle (f*g)(x)=\sum_{d|x}d^2\varphi(d)g(\frac{x}{d})=\sum_{d|x}\varphi(d)x^2=x^3\)

我们有 \(\displaystyle\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6},\sum_{i=1}^ni^3=\left(\sum_{i=1}^ni\right)^2=\frac{n^2(n+1)^2}{4}\)

于是可以杜教筛了。