[探究] $\mu$函数的性质应用

参考的神仙An_Account的blog，膜一下。

其实就是一类反演问题可以用$\mu$函数的性质直接爆算出来。

然后其实性质就是一个代换：

\[\sum_{d|n}\mu(d)=[n=1]\]

问题一：求

\[\sum_{i=1}^n\sum_{j=1}^m[i \perp j]\]

……然而其实就是

\[\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\mu(d)\]

考虑$d|\gcd(i,j)$就是$d|i,d|j$，于是可以枚举$d$。

\[\sum_{d=1}^{\min(n,m)}\mu(d)\cdot \lfloor\frac{n}{d}\rfloor\cdot \lfloor\frac{m}{d}\rfloor\]

这东西就可以直接分块。

问题二：求

\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]\]

然而根据一个定理：

\[\gcd(i,j)=k\Longrightarrow\gcd(\frac{i}{k},\frac{j}{k})=1\]

于是就变成了：

\[\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[i \perp j]\]

问题三：求

\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k],k\in\rm{Prime}\]

我们考虑现在的柿子其实长这样：

\[\sum_{k\in \rm{Prime}}\sum_{d=1}^{\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\cdot \lfloor\frac{n}{kd}\rfloor\cdot \lfloor\frac{m}{kd}\rfloor\]

一个思想就是不断把重复求和的东西提到前面去。我们发现似乎带有$kd$的几项被重复求和，效率很低。同时因为$O(kd)=O(n)$，所以改成先枚举$kd$:

\[\begin{aligned}p=kd\\ \sum_{p=1}^{\min{(n,m)}}\end{aligned}\lfloor\frac{n}{p}\rfloor\cdot \lfloor\frac{m}{p}\rfloor\sum_{d|p}\mu (d)\]

然后显然后面的那个$\sum$是可以预处理的，于是就还是$O(\sqrt n)$的分块。

后面的择日应该会学一学= =？

巴特西

[探究] $\mu$函数的性质应用

问题一：求

问题二：求

问题三：求

最新文章

热门文章