数学 · 初探莫比乌斯

· · 个人记录

我向莫反的门中望了仅仅一眼，就望而却步。

本篇是初探，大佬们请移步。本篇不用任何基础，需要略懂容斥，线性筛，整除分块，组合，不会的这里也会讲。

首先介绍一下神奇的莫比乌斯函数：

将 N 质因数分解得：N = p_1^{c_1}p_2^{c_2}……p_m^{c_m}

\\1&\forall i, c_i=1,m\equiv0\pmod{2} \\-1&\forall i, c_i=1,m\equiv1\pmod{2}\end{cases}

我其实是从容斥那里接触到莫比乌斯的。这个函数也和容斥原理有千丝万缕的关系。

举个例子。如果我们想快速算出 1-N 中和 a 互质的数的个数，可以怎么算呢？ 我们设 S(i) 代表 1-N 中和 a 有公质因子 i 的数的个数，显然我们可以很轻松算出 S(i) （若 a 没有 i 这个质因子就为 0, 否则就为 \left\lfloor\dfrac{N}{i}\right\rfloor ）。

一共有 S(1) 个数，我们只需要其中和 a 只有公因子 1 的。就要减去公因子不为 1 的，即为 S(2),S(3),S(5) 等等。但是我们减的同时把公因子是 6,10,15 这样的多减了一遍，又要加回来。这时候就需要用到容斥了。而我们发现，由容斥可得的 S(i) 的系数恰好就是莫比乌斯函数！！ (奇数个就减，偶数个就加！)

那答案就是 \sum\limits_{i=1}^N\mu(i)*S[i] 。

这里我们稍微运用一下整除分块，发现 \left\lfloor\dfrac{N}{i}\right\rfloor 这玩意最多有 2\sqrt{N} 种取值，为什么？当 i<\sqrt{N} 时，最多产生 \sqrt{N} 个，每个 i 都对应一个。 当 i>\sqrt{N} 时，\left\lfloor\dfrac{N}{i}\right\rfloor<\sqrt{N} ，也最多产生 \sqrt{N} 个。因为值域就是 \sqrt{N}。

那我们就可以维护 \mu(i) 的前缀和，将相同的 S[i] 合并一起算，最多算 2\sqrt{N} 次。

计算 \mu(i) 可以用到线性筛法。

线性筛：

相信大家早已学过线性筛素数 ( 没学过这个来学莫比乌斯？ )。其原理大概就是让每个数只被自己最小的质因子筛一次，这里不再细说。

这里只需要在枚举质因子时判断一下是否含有两个相同的。其余情况每多一个质因子乘一下 -1 即可。

for (int i = 1; i < maxn; i++) miu[i] = 1;
for (int i = 2; i < maxn; i++){
    if (!mn[i]){
        miu[i] = -1;
        mn[i] = i;
        p[++m] = i;
    }
    for (int j = 1; j <= m; j++){
        if (p[j] > mn[i] || i*p[j] >= maxn) break;
        mn[i*p[j]] = p[j];
        if (i%p[j] == 0) miu[i*p[j]] = 0;
        else miu[i*p[j]] = -miu[i];
    }
}

性质：

莫比乌斯函数有一个很重要的性质，就是 \sum\limits_{d|n}\mu(d) = [n = 1]。 这个式子的意思就是 [n=1] 时，前面式子值为 1, 否则为 0。

我们来证明一下：

将 n 质因数分解得：

但我们发现其中有很多项其实不用算，比如 $\mu(p_1^{2}p_2^{3})$ 这一项。因为根据定义，含有质因数指数大于 $1$ 的数，莫比乌斯函数值都是 $0$。 我们就可以来算 $n = p_1p_2……p_m$ 时 $\sum\limits_{d|n}\mu(d)$ 的值，和刚刚是等价的。 直接暴力计算，从 $m$ 个数任取 $i$ 个，方法有 $C^i_m$ 种， 函数值根据定义就是 $(-1)^i$。 所以 $\sum\limits_{d|n}\mu(d) = \sum\limits_{i=0}^kC^i_m*(-1)^i$ 。 这是什么，是二项式定理呀！[不会看这里](https://www.luogu.com.cn/blog/lgzhou/shuo-xue-zu-ge-shuo-xue-ji-chu)。 当 $k = 0$ 时，即 $n = 1$ 时式子为 $1$，其他时候该式子为零。 *** **例题：** [P3455 [POI2007]ZAP-Queries](https://www.luogu.com.cn/problem/P3455)。 原题可以等价于求有多少 $x\leqslant a/d,y \leqslant b/d$。且 $x,y$ 互质。 设 $n = a/d, m = b/d$，我们后面还要用到 $d$ 这个变量。 我们可以把 $gcd(x,y)$ 套进去刚才那个性质 $\sum\limits_{d|gcd(x,y)}\mu(d) = [gcd(x,y) = 1]$。 那我们只用枚举每一对 $x,y$，再算出 $\sum\limits_{d|gcd(x,y)}\mu(d)$ 相加就是答案。 即 $\sum\limits_{x=1}^{n} \sum\limits_{y=1}^{m} \sum\limits_{d|gcd(x,y)}\mu(d)

但这样复杂度就爆炸了（你都算出来 gcd(x,y) 了还管什么 \mu）。

有点像主元法，我们枚举每一个 d，看看有多少对 x,y 满足 d|gcd(x,y)。 跟上一道题一样，显然有

最后答案 $=\sum\limits_{d = 1}^{min(n,m)}\mu(d) \left\lfloor\dfrac{n}{d}\right\rfloor \left\lfloor\dfrac{m}{d}\right\rfloor

依旧用整除分块维护 \mu 的前缀和就可以可快速处理。


for (int d = 1; d <= min(n,m); d = up){
    up = min(n/(n/d)+1,m/(m/d)+1);
    ans += (sum[up-1]-sum[d-1])*((n/d)*(m/d));
}//sum是 miu 的前缀和

这个性质还可以解决很多问题。 具体请看：数学 · 初探莫比乌斯2