简单的数学题

Posted on 2020-08-14 Edited on 2023-10-26 In OI , 算法 Views:

luogu3768

luogu3768 简单的数学题题解

题意:求

$\Sigma_{i=1}^n\Sigma_{j=1}^n ijgcd(i,j)$

这个式子看起来很基础，但是可以看到数据范围大于$1e8$，求和上指标又同为$n$,此题肯定有一些特殊的做法

先按照常规的套路，设

$d=(i,j)$

并将$d$直接提出来

$\Sigma_{d=1}^nd^3 \Sigma_{i=1}^{n/d}\Sigma_{j=1}^{n/d}ij[(i,j)=1]$

右边的式子用莫比乌斯函数的和式替代

$\Sigma_{d=1}^nd^3 \Sigma_{i=1}^{n/d}\Sigma_{j=1}^{n/d}ij\Sigma_{k|(i,j)}\mu(k)$

将$k$往左边提

$\Sigma_{d=1}^nd^3 \Sigma_{k=1}^{n/d}k^2\mu(k)(\Sigma_{i=1}^{n/kd}i)^2$

设右边的和式为$c$,并用$T=kd$换元

$\Sigma_{d=1}^nd^3 \Sigma_{T=1}^n c(T)^2(T/d)^2\mu(T/d)$

整理式子

$\Sigma_{T=1}^nc(T)^2T^2\Sigma_{d|T}d\mu(T/d)$

根据狄利克雷卷积的性质

$\varphi=\mu*id$

可以将右边的式子用$\varphi$代替

$\Sigma_{T=1}^n c(T)^2T^2\varphi(T)$

观察右侧的式子，可以发现$T^2\varphi(T)$是一个积性函数(两个数论函数的积仍为积性函数)，考虑处理这一部分，试图用杜教筛的式子向上套

$g(1)S(n)=\Sigma_{i=1}^nH_i-\Sigma_{i=2}^ng(i)S(n/i)$

其中

$S(n)=\Sigma_{i=1}^nf(i),H=f*g,f(n)=n^2\varphi(n)$

观察$f(n)$，$\varphi$难以直接处理，肯定要被转化掉，那就利用狄利克雷卷积中的$id=I*\varphi$,设$g(n)=1$则

$H(n)=n^2\Sigma_{d|n}\varphi(d)=n^3$

通过解递推方程可以发现，$\Sigma_{i=1}^nH_i$就是原式中的$c^2$,于是式子的形式就很简洁了

$S(n)=c(n)^2-\Sigma_{i=2}^ni^2S(n/i)$

直接代入原式求解就可以辣

小结:此题在莫反的基础上有扩展，上指标相同看似简化条件，实际上对性能要求更高。推式子时利用了狄利克雷卷积来处理$\mu$,并在最后杜教筛处理前缀和时再次利用了$\varphi$的性质，算是对数论函数关系的灵活拓展