背景：

一道好题，根据大佬的$blog$学的。

题目传送门：

https://www.luogu.org/problemnew/show/SP20173

题意：

求${\sum }_{i=1}^n\sigma (i^2)$。
其中$\sigma (n)$表示$n$的约数个数。

思路：

$$\sum _{i=1}^n\sigma (i^2)$$
考虑$x=p_1^{a_1}{p}_2^{a_2}...p_k^{a_k}$，则$\sigma (x)={\prod }_{i=1}^k(a_i+1)$；
则$x^2=p_1^{2a_1}{p}_2^{2a_2}...p_k^{2a_k}$，则$\sigma (x)={\prod }_{i=1}^k(2a_i+1)$。
则原式子
$$=\sum _{i=1}^n\prod _{j=1}^k(2a_j+1)$$
考虑${\prod }_{j=1}^k(2a_j+1)$的暴力求解，就是若干个$a$与其它的$1$暴力匹配，那不妨写成子集枚举的形式。
= ∑ i = 1 n ∑ S ⊆ { 1 , 2 , . . . , k i } 2 ∣ S ∣ ∏ j ∈ S a j =sum_{i=1}^{n}sum_{S⊆{1,2,...,k_i}}2^{|S|}prod_{j∈S}{a_j} =i=1∑n​S⊆{1,2,...,ki​}∑​2∣S∣j∈S∏​aj​
事实上，若存在$a_j=0$，那就没有贡献。那有贡献的就是$i$的约数。
每个约数的贡献是$2^{\omega }(d)$，其中$\omega (i)$表示$i$的质因数个数，所以就有：
$$=\sum _{i=1}^n\sum _{d|i}{2}^{\omega (d)}$$
其实把$\omega (d)$看成每个质因数选或不选，就是$d$的无平方约数的个数。则$2^{\omega (d)}={\sum }_{p|d}{\mu }^2(p)$。

设$f_n=\sigma (n^2),g_n=2^{\omega (d)},h_n={\mu }^2(n)$。
则有：$f=g\ast I,g=h\ast I$（由上面的式子写成狄利克雷卷积的形式），
则有：$f=(h\ast I)\ast I=h\ast (I\ast I)=h\ast \sigma$（狄利克雷卷积结合律），所以有：
$$\sum _{i=1}^n{f}_i=\sum _{i=1}^n(h\ast \sigma )(i)=\sum _{ij\le n}{h}_i{\sigma }_j=\sum _{i=1}^n{\mu }_i^2\sum _{j=1}^{\lfloor \frac{n}{i}\rfloor }{\sigma }_j$$
显然我们就需要算出${\mu }^2,\sigma$的前缀和。
${\sum }_{i=1}^n{\sigma }_n={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$
那么${\sum }_{i=1}^n{\mu }_i^2$的求法就是$[1,n]$中无平方约数的个数和。
证明就是$\mu$函数的性质：一个数$x$为完全平方数的整数倍时，${\mu }_x=0$；否则${\mu }_x=\pm 1,{\mu }_x^2=1$，所以得证。
考虑容斥原理，就有${\sum }_{i=1}^n{\mu }_i^2={\sum }_{i=1}^{\sqrt{n}}{\mu }_i\lfloor \frac{n}{i^2}\rfloor$。
等用于：完全平方数。
套在一起用整除分块即可。

代码：

goto

最后

以上就是强健黑裤为你收集整理的luogu SP20173 DIVCNT2 - Counting Divisors (square)背景：题目传送门：题意：思路：代码：的全部内容，希望文章能够帮你解决luogu SP20173 DIVCNT2 - Counting Divisors (square)背景：题目传送门：题意：思路：代码：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。