简单的数学题

求 $(\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j))\bmod p$

推式子：

\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j) &= \sum_{i=1}^n\sum_{j=1}^nij\sum_{d\mid \gcd(i,j)}\varphi(d)\\ &= \sum_{d=1}^n\varphi(d)\sum_{d\mid i}\sum_{d\mid j}ij \\ &= \sum_{d=1}^n\varphi(d)\times d^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij\\ &= \sum_{d=1}^n\varphi(d)\times d^2(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i)^2\\ \end{aligned}$$ 注意到后面的玩意可以整除分块，前面这个 $f(n)=\varphi(n)\times n^2$ 可以卷一个 $g(n)=n^2$，得到 $h(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})=n^2\sum_{d\mid n}\varphi(d)=n^3$，注意到 $G(n)=\frac{n(n+1)(2n+1)}{6}, H(n)=\frac{n^2(n+1)^2}{4}$，杜教筛即可

文章操作