您的位置: 首页  >  IT文章  >  「从零开始的莫比乌斯反演」2. 莫比乌斯函数

「从零开始的莫比乌斯反演」2. 莫比乌斯函数

分类: IT文章 • 2022-06-15 20:30:40

看到这个标题没，它的标号是2，说明肯定还有个0和1。

莫比乌斯函数，它是一个函数。。。

定义

[mu(n) = egin{cases} 1 & (n = 1) \ (-1)^k & n = prodlimits_{i = 1}^{k} p_i \ 0 & otherwise end{cases} ]

其中，(p_i)为互不相同的素数。

本章完

稍微解释一下：莫比乌斯函数的意思是：

  1. (n = 1)时，(mu(n) = 1)；
  2. (n)肯定由若干质数相乘得到（大于(1)的任何正整数都能分解质因数）。如果乘起来得到(n)的这一堆质数里，没有相互重复的，那么(mu(n) = (-1)^{k})，(k)是(n)质因子的个数；
  3. 剩下的情况（就是有重复质因子），(mu(n) = 0)

性质

性质0：莫比乌斯函数是积性函数

积性函数指对于所有互质的整数(a)和(b)，有性质(f(ab)=f(a)f(b))的数论函数

——《百度百科》

这个百科定义还挺简洁的，就不解释了QwQ

显然，莫比乌斯函数是积性函数

下面给出证明，这个证明比较简单，而且我自己写得比较乱，不想看可以跳过。

显然，当(n = 1)时，对于任意正整数(m)，有(mu(1) cdot mu(m) = mu(1 cdot m))；

对于(mu(n) = 0)，显然，(n = prod p_i^{a_i})，且存在某个(a_i > 1)。那么，对于任意正整数(m)，有(mn = prod p_i^{a_i})，且存在某个(a_i > 1)，故(mu(mn) = 0 = mu(m) cdot mu(n))；

对于(n > 1, m > 1)，且(mu(n) cdot mu(m) eq 0)，当(operatorname{gcd}(n, m) = 1)时，它们没有相同的质因子，故(mn = prod p_i^{a_i})，且对于所有(i)，都有(a_i = 1)。故有(mu(n) cdot mu(m) = (-1)^{k_1 + k_2})。

(sumlimits_{d|n}mu(d) = 0)

这条性质还可以换个说法：

令(varepsilon(n) = sumlimits_{d|n}mu(d))，那么：

[varepsilon(n) = egin{cases} 1 & n = 1 \ 0 & n > 1 end{cases} ]

这条性质超级重要，一定要弄明白，后面狄利克雷卷积还要用到它（其实是上面那个(varepsilon(n))）。

证明为了保证相对严谨，可能有一点枯燥。总体来说就是排列组合+二项式定理。实际上是一个高中很常用的做题技巧。

(n = 1)时，(sumlimits_{d|n} mu(d) = 1)。这是显然的。

下证： (n > 1)时，(sumlimits_{d|n}mu(d) = 0)。

假设，(mu(n) eq 0, n = prodlimits_{i = 1}^{k}p_i^{a_i})，其中(p_i)为互不相同的质数（下同）。那么，由(mu(n) eq 0)可知，(a_i)恒为(1)。

那么，我们重新理解(d|n)。能整除(n)的数，它一定由一个或多个(p_i)相乘得得到。而且，这些(p_i)任意组合，它们相乘得到的数，一定能整除(n)。所以，现在我们考虑，将这些(p_i)组合，看看得到的结果。

当(d)由偶数个(p)（包括(0)，因为(1)也要考虑）构成时，显然(mu(d) = 1)；当(d)由奇数个(p)构成时，(mu(d) = -1)。

那么，(sumlimits_{d|n}mu(d) = C_{k}^{0} - C_{k}^{1} + cdots + (-1)^{k}C_{k}^{k})。

我们考虑((a + b)^n)，将其展开，得到：

[C_{n}^{0} a^n + C_{n}^{1} a^{n-1}cdot b + cdots + C_{n}^{n}b^n ]

显然，我们将(a = 1, b = -1)代入，展开，即可得上式。而(a = 1, b = -1)时，显然((a + b)^n = 0)恒成立。故(sumlimits_{d|n}mu(d) = C_{k}^{0} - C_{k}^{1} + cdots + (-1)^{k}C_{k}^{k} = 0)恒成立。

([operatorname{gcd}(i,j) = 1] Longleftrightarrow sumlimits_{d|operatorname{gcd}(i,j)}mu(d))

根据上一点性质，显然，(operatorname{gcd}(i,j) = 1)时，代入(n)，容易得到，等式右侧的值也为(1)。反之，则为(0)。

线性筛

莫比乌斯函数是积性函数，所以也是可以线性筛的。

我们枚举(i)的时候，显然如果(i)是质数，那么mu[i] = -1；

否则，我们枚举prime[j]的时候，i * prime[j]的质数个数一定恰好比i多一个。所以，mu[i * prime[j]] = -mu[i]；

最后，如果i % prime[j] == 0，说明i * prime[j]是有重复质因子的，此时mu[i * prime[j]] = 0（全局变量默认就是(0)，所以没有特别写）。

代码：

int prime[maxn], numprime, mu[maxn];
bool isprime[maxn];

void make_mu(const int &up_bound) {
    isprime[0] = isprime[1] = 1;
    mu[1] = 1;
    for (int i = 2; i < up_bound; i++) {
        if (!isprime[i]) {
            prime[numprime++] = i;
            mu[i] = -1;
        }
        for (int j = 0; j < numprime && i * prime[j] < up_bound; j++) {
            isprime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i < up_bound; i++) mu[i] += mu[i - 1];
}

PS：这个代码是提交过题目的，放心用QwQ

相关推荐