关于∑n div i的求法

求\(\sum{\left \lfloor \frac{n}{i} \right \rfloor}\)

慢且麻烦的一般方法:

设 \(s=\left \lfloor \sqrt{n} \right \rfloor\)

对于s<=的暴力计算,>s的分块算

常数很大

考虑\(\sum{\left \lfloor \frac{n}{i} \right \rfloor}\)的意义,发现等同于求(x,y)使得xy<=n的对数

把图画出来,图像必然根据y=x对称

关于∑n div i的求法

求出s<=的部分sum,这一部分等于左下角的s*s方形+上面的部分,根据对称性上面的等于右边的

因此\(\sum{\left \lfloor \frac{n}{i} \right \rfloor}=2sum-s^2\)

上一篇:Harbour.Space Scholarship Contest 2021-2022 题解


下一篇:【题解&总结】 P3327 [SDOI2015]约数个数和