简单的数学题
DJ_Liu
·
·
个人记录
简单的数学题
求 (\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},杜教筛即可