『Möbius函数与Möbius反演』

时间：2023-03-08 21:47:19

<更新提示>

<第一次更新>

<正文>

Möbius函数

定义

设正整数\(n\)算数基本定理分解后为\(n=\prod_{i=1}^{k}p_i^{a_i}\)，定义函数

\[\mu(n)=
\begin{cases}
0\ \ (\exists\ i\in[1,k],a_i>1)
\\(-1)^k\ \ (\forall\ i\in[1,k],a_i=1)
\end{cases}
\]

称\(\mu(n)\)为\(Möbius\)函数。

即分解质因数后，若\(n\)有多个相同的质因子，则\(\mu(n)=0\)。当\(n\)的的质因子各不相同时，若\(n\)有偶数个质因子，则\(\mu(n)=1\)，若\(n\)有奇数个质因子，则\(\mu(n)=-1\)。

求解

对于单个数字的\(Möbius\)函数，可以直接用试除法分解质因数求解，时间复杂度为\(O(\sqrt n)\)。若要求求解\(1-n\)的所有\(Möbius\)函数，则可以配合线性筛求解：

\(1.\) 对于线性筛找到的一个质数，显然\(\mu(n)=-1\)

\(2.\) 对于线性筛用最小质因子\(p_j\)筛掉一个合数时，由\(Möbius\)函数定义的第二部分可得\(\mu(i*p_j)=-\mu(i)\)

\(Code:\)

inline void sieve(void)

{

    mui[1] = 1;

    for (int i=2;i<=Uplim;i++)

    {

        if (!vis[i])Prime[++cnt] = i , mui[i] = -1;

        for (int j=1;j<=cnt&&i*Prime[j]<=Uplim;j++)

        {

            vis[ i*Prime[j] ] = true;

            if (i%Prime[j]==0)break;

            mui[ i*Prime[j] ] = -mui[i];

        }

    }

}

性质

\(1.\) 对于任意正整数\(n\)，若\(n=1\)，则\(\sum_{d|n}\mu(d)=1\)，若\(n>1\)，则\(\sum_{d|n}\mu(d)=0\)。

证明：

当\(n=1\)时，\(\sum_{d|n}\mu(d)=1\)显然成立。

当\(n>1\)时，令\(n=\prod_{i=1}^kp_i^{a_i}\)，则\(n\)的因数中\(\mu\)值不为\(0\)的必然是由若干个互不相同的质因子相乘得到的，其中质因子个数为\(r\)的有\(C_k^r\)个，那么显然有\(\sum_{d|n}\mu(d)=\sum_{i=0}^k(-1)^iC_k^i\)，此式恰为二项式定理\((a+b)^n=\sum_{i=0}^nC_n^ia^ib^{n-i}\)中代入\(a=-1,b=1,n=k\)的情况，可知\(\sum_{d|n}\mu(d)=(-1+1)^k=0\)。

\(2.\) 对于任意正整数\(n\)，有\(\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}\)。

证明：

因为\(n=\sum_{d|n}\phi(d)\)，令\(F(n)=n,f(n)=\phi(n)\)，则由莫比乌斯定理可得\(\phi(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(d)*\frac{n}{d}\)，所以可得\(\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}\)。

\(3.\) \(Möbius\)函数为积性函数，即对于互质正整数\(a,b\)，有\(\mu(a*b)=\mu(a)*\mu(b)\)。

证明略。

Möbius反演

Möbius定理

首先，我们需要先了解\(Möbius\)反演的基础，\(Möbius\)定理。

\(Möbius\)定理：

\(1.\) 因数形式：若数论函数\(F,f\)满足\(F(n)=\sum_{d|n}f(d)\)，则可以得到\(f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\)。

\(2.\) 倍数形式：若数论函数\(F,f\)满足\(F(n)=\sum_{n|d}f(d)\)，则可以得到\(f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)\)。

证明：

因数形式

\[\sum_{d|n}\mu(d)F(\frac{n}{d})\\=\sum_{d|n}\mu(d)\sum_{d'|\frac{n}{d}}f(d')=\sum_{d'|n}f(d')\sum_{d|\frac{n}{d'}}\mu(d)
\]

由于\(Möbius\)的性质\(1.\)可得\(\sum_{d|n}\mu(d)=1\)当且仅当\(n=1\)，所以对于\(\sum_{d|\frac{n}{d'}}\mu(d)\)非\(0\)，当且仅当\(\frac{n}{d'}=1\)，即\(n=d'\)，所以有

\[\sum_{d'|n}f(d')\sum_{d|\frac{n}{d'}}\mu(d)=f(n)
\]

倍数形式

设\(\frac{d}{n}=k\)，则可以得到

\[\sum_{n|d}\mu(\frac{d}{n})F(d)
\\=\sum_{k=1}^{+\infty}\mu(k)F(nk)=\sum_{k=1}^{+\infty}\mu(k)\sum_{nk|t}f(t)
\\=\sum_{n|t}f(t)\sum_{k|\frac{t}{n}}\mu(k)
\]

由于\(Möbius\)的性质\(1.\)可得\(\sum_{d|n}\mu(d)=1\)当且仅当\(n=1\)，所以对于\(\sum_{k|\frac{t}{n}}\mu(k)\)非\(0\)，当且仅当\(\frac{n}{t}=1\)，即\(n=t\)，所以有

\[\sum_{n|t}f(t)\sum_{k|\frac{t}{n}}\mu(k)=f(n)
\]

应用

在某些题目中，若有某个函数\(f\)的值比较难求，但是其自变量倍数或约数的函数值求和\(F\)函数比较好求，可以先求出函数\(F\)的值，再利用\(Möbius\)定理，反演求出原函数的值。

<后记>

相关文章