简单的数学题

· · 个人记录

简单的数学题

(\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},杜教筛即可