莫比乌斯函数及有关性质

author: lyn

定义

莫比乌斯函数 \(\mu\) 的定义如下：

\[\mu(n)= \begin{cases}1&n=1\\(-1)^s& n=p_1p_2...p_s\\ 0&\exist i,p_i^2|n\\ \end{cases}\]

容易发现，莫比乌斯函数为积性函数。

性质

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

当 \(n=1\) 时，原式显然成立。

当 \(n\) 不为 \(1\) 时，我们设 \(n=p_1^{a_1}p_2^{a_2}...p_s^{a_s},n=p_1p_2...p_s\)

由于同时选到多个同种质因子时 \(\mu(d)=0\) ，所以我们只考虑一种质因子至多选一个的情况。

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

接下来我们分别考虑选 \(0\) 个质因子，选 \(1\) 个质因子...选 \(s\) 个质因子的情况。

由于选奇数个质因子时 \(\mu(d)=-1\) ，选偶数个质因子时 \(\mu(d)=1\) 。

原式可表示为

\[\mu(n)=(-1)^0C_s^0+(-1)^1C_s^1...+(-1)^sC_s^s\]

学过二项式定理的都知道，这就是 \((1+(-1))^s\) 的展开形式。

所以原式在 \(n\) 不为 \(1\) 时恒为 \(0\) 。

---

此外，莫比乌斯函数 \(\mu\) 和欧拉函数 \(\varphi\) 之间还有着神奇的联系：

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

我们同样设 \(n=p_1^{a_1}p_2^{a_2}...p_s^{a_s},n=p_1p_2...p_s\)

那么原式可表示为 \(n\sum_{d|n}\frac{\mu(d)}{d}\)

分别考虑选 \(0\) 个质因子，选 \(1\) 个质因子...选 \(s\) 个质因子的情况。

则有

\[n\sum_{d|n}\frac{\mu(d)}{d}=n(1-(\frac{1}{p_1}+\frac{1}{p_2}...+\frac{1}{p_s})+(\frac{1}{p_1p_2}+...)-...)\]

注意到， \(n\) 后面的系数就是 \((1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_s})\) ，没注意到的可以自己举个例子试试。

那么原式就是 \(\sum_{d|n}(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_s})\)

也就是 \(\varphi(n)\) 。

线性筛求莫比乌斯函数

利用线性筛可以 \(O(n)\) 求出 \(\mu(1) \sim \mu(n)\) 的值。

实现

void getmu(int n)
{
    isprime.set();
    mu[1] = 1;
    for (ll i = 2; i <= n; i++)
    {
        if (isprime[i])
        {
            mu[i] = -1;
            pri.emplace_back(i);
        }
        for (ll j : pri)
        {
            if (i * j > n)
                break;
            isprime[i * j] = 0;
            if (i % j == 0)
            {
                mu[i * j] = 0;
                break;
            }
            mu[i * j] = -mu[i];
        }
    }
}