莫比乌斯函数与莫比乌斯反演

积性函数之间常常藏着一层「先对约数求和，再还原成点值」的关系。欧拉函数、互素计数、无平方因子的指示，最后都会碰到同一个开关：莫比乌斯函数 $\mu(n)$。下面把定义、那条几乎处处为零的求和恒等式、反演公式，以及筛法实现放在一条线上。

莫比乌斯函数怎么取值

对正整数 $n$，先写素因子分解 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$。莫比乌斯函数 只看两件事：有没有平方因子，以及不同素因子的个数。

换句话说：

• $1$ 的值是 $1$
• 无平方因子且有偶数个不同素因子，值为 $1$
• 无平方因子且有奇数个不同素因子，值为 $-1$
• 被某个素数的平方整除，值为 $0$

几个具体值：$\mu(1)=1$，$\mu(2)=-1$，$\mu(3)=-1$，$\mu(6)=\mu(2\cdot 3)=1$，，。再看 ，四个不同素数，所以 ；而 含平方，所以 。

判断时不要先数「全部素因子的个数再取符号」，而要先问有没有平方。$18=2\cdot 3^2$ 有三个素因子因子，但 $\mu(18)=0$，不是 $-1$。手算可以先试除平方数 $4,9,25,49,\ldots$，能整除就直接停。

$\mu$ 是积性函数：若 $\gcd(a,b)=1$，则 $\mu(ab)=\mu(a)\mu(b)$。它不是完全积性的。$\mu(4)=0$，但 。只要出现平方，对任意分解直接相乘就会错。写筛法时记住：合数的值可以由互素因子乘出来，但不能对带平方的分解随便乘。

那条核心恒等式

莫比乌斯函数真正有用，是因为它和常数函数 $1$ 互为狄利克雷逆。写成求和就是

右边是艾弗森括号：$n=1$ 时为 $1$，否则为 $0$。

先看几个数。

• $n=1$：只有 $d=1$，和为 $\mu(1)=1$。
• $n=p$：约数是 $1,p$，和为 。

一般证明走素因子。设 $n$ 有 $k$ 个不同素因子。因为 $\mu$ 在有平方因子的约数上为零，求和只剩下从这 $k$ 个素数里任选一个子集。选 $t$ 个素数的项贡献 $(-1)^t$，这样的子集有 $$ 个。于是

约定 $0^0=1$，所以 $k=0$（即 $n=1$）时得 $1$，否则得 $0$。这就是 。

数论里「恰好等于 $1$」「恰好互素」经常被写成这种指示。容斥原理的符号 $(-1)^k$ 和 $\mu$ 是同一套东西：对每个素数选或不选，平方因子直接杀掉。

也可以从生成函数看一眼。若只看无平方核，每个素数贡献因子 $(1-1)=0$，所以合数的约数和抵消干净；只有完全没有素数可贡献时，空积等于 $1$。这和「容斥到最后空集合留下 $1$」是同一句话。

用 $n=30$ 把约数和写全：约数 $1,2,3,5,6,10,15,30$，对应 $\mu$ 为 $1,-1,-1,-1,1,1,1,-$，加起来 。任意 都会这样成对消掉。这条恒等式后面会被反复当作「内层求和的开关」：它要么给出 ，要么整段消失。

莫比乌斯反演

设 $f$、$g$ 是定义在正整数上的两个函数。若对每个 $n$ 都有

则

也可以写成 $f(n)=\sum_{d \mid n}\mu(n/d)\,g(d)$，只是把约数配对换了一下。反过来也对：从第二式能推回第一式。这一对互推就叫莫比乌斯反演。

还有一种「整除方向反过来」的形式，竞赛里同样常见。若

在只对有限多项求和时，

第一种按约数从下往上累加，第二种按倍数从下往上累加。下面证明用第一种。两种写法只是偏序反过来，不要在同一道题里各用一半，否则求和下标就很容易对不上。

证明思路

把第二式的右边展开。代入 $g(n/d)=\sum_{e \mid (n/d)} f(e)$，得到

对满足 $d \mid n$ 且 $e \mid (n/d)$ 的对 $(d,e)$ 求和。改成先固定 $e$，再对 $d \mid (n/e)$ 求和：

内层恰好是上节的恒等式，等于 $[n/e=1]$，也就是只有 $e=n$ 时为 $1$。于是整段塌成 $f(n)$。

反过来，从 $f$ 推 $g$ 时，把 $\mu$ 的求和再叠一层，内层又变成 $\sum_{d \mid m}\mu(d)=[m=1]$，同样只留下一项。

不必把它想成矩阵求逆的黑箱。狄利克雷卷积下，$1*\mu=\varepsilon$，其中 $1$ 是恒为 $1$ 的函数，$\varepsilon$ 是单位元（$\varepsilon(1)=1$，其余为 $$）。于是 当且仅当 。反演就是两边同时卷积 。

用一个具体的 $n$ 把换序看清楚。取 $n=6$，$g(n)=\sum_{d\mid n}f(d)$，要还原 $$。公式给出

把每个 $g$ 展开：

代入后 $f(1)$ 的系数是 $1-1-1+1=0$，$f(2)$ 的系数是 $1-1=0$， 的系数是 ，只剩下 。系数恰好是 。一般 也是这样：每个 前面挂着 。

经典例子：欧拉函数

欧拉函数 $\varphi(n)$ 表示 $1$ 到 $n$ 中与 $n$ 互素的个数。它有一条更老的恒等式：

原因是：把 $\{1,2,\dots,n\}$ 按 $\gcd(k,n)$ 分组。若 $\gcd(k,n)=d$，则 $$ 与 互素，这样的 恰有 个。对所有 求和得到 。换元后就是 。

现在 $g(n)=n$，$f=\varphi$，反演立刻给出

这就是用 $\mu$ 写 $\varphi$ 的公式。手算 $n=12$：约数 $1,2,3,4,6,12$，对应 $\mu$ 为 ，于是

$1,5,7,11$ 确实与 $12$ 互素。

若已经会素因子公式 $\varphi(n)=n\prod_{p\mid n}(1-1/p)$，会发现它和上式是同一件事：展开乘积，每一项正好对应无平方约数上的 $\mu(d)/d$。

互素指示也可以从同一条恒等式读出来。$\gcd(k,n)=1$ 当且仅当 $\sum_{d \mid \gcd(k,n)}\mu(d)=1$。于是

又回到 $\varphi(n)$。很多「与 $n$ 互素」的计数，第一步都是把 $[\gcd=1]$ 换成 $\mu$ 的和，再交换求和顺序。例如 $1$ 到 $n$、$$ 到 的互素对数

就是把指示函数展开再换序。整除分块可以把相同的 $\lfloor n/d\rfloor$ 段压成 $O(\sqrt{n})$。

再手算一次 $n=9$。约数 $1,3,9$，对应 $\mu$ 为 $1,-1,0$，于是

$1,2,4,5,7,8$ 与 $9$ 互素，对得上。注意 $9=3^2$ 使 $\mu(9)=0$，反演时这一项直接不出现；漏把平方约数的 置零，就会多减或多加。

另一个常见变形是对 $\gcd$ 求和。由 $\sum_{d\mid n}\varphi(d)=n$ 可以推出

若题目要的是「先知道约数和，再求原函数」，就走反演；若已经有 $\varphi$ 的显式，直接代入往往更短。两者并不冲突，只是从哪一头写起不同。

线性筛求 $\mu$

埃氏筛对每个合数会标多次。线性筛保证每个合数只被最小质因子划掉一次，同时可以把积性函数的值递推出来。对 $\mu$ 的规则是：

• $\mu(1)=1$
• 若 $i$ 乘上一个新素数 $p$，且 $p \nmid i$，则 $\mu(ip)=-\mu(i)$

时间 $O(n)$。vis[i] 为假表示 $i$ 是素数，此时直接赋 $\mu(i)=-1$。内层一旦发现 $p$ 整除 $i$，说明最小质因子已经用过，break 保证每个合数只进入一次。跑一下就能对上前面的手算：$\mu(1)$ 到 是 。

线性筛和积性是绑在一起的。当 $p\nmid i$ 时 $\gcd(i,p)=1$，所以 $\mu(ip)=\mu(i)\mu(p)=-\mu(i)$。当 时， 至少含 ，定义直接给出 ，不必再访问更大的素数。若漏掉 ，同一个合数会被多个质因子更新，后面的赋值会把已经正确的 改乱。

预处理出 mu 之后，单个 $n$ 的反演就是枚举约数。约数个数通常很小，比再筛一次便宜。需要 $\varphi$ 的整段前缀时，也可以在同一套线性筛里顺带递推 $\varphi$，不必每次再对约数求和。

若只要单个 $n$ 的 $\mu(n)$，不必筛到 $n$。试除到 $\sqrt{n}$，统计不同素因子个数，中途碰到平方因子就返回 $$。

写的时候容易踩的坑

$\mu(1)$ 是 $1$，不是 $0$。很多循环从 $2$ 开始筛，却忘了初始化 mu[1]。后面反演时 $d=1$ 那一项正好是 $g(n)$ 自己，漏了整式就错。

有平方因子必须是 $0$，不是 $(-1)$ 的某种次数。$\mu(12)=\mu(2^2\cdot 3)=0$，不是 $\mu (2$。线性筛里「 整除 就置 并 」就是在落实这件事。

反演的求和下标是 $d \mid n$，不是 $d \le n$。写成 $\sum_{d=1}^{n}\mu(d)g(n/d)$ 而不加整除条件，只有在 被定义成「非整数处为 」时才碰巧对；一般函数会多算许多项。

两种反演不要混。$g(n)=\sum_{d\mid n}f(d)$ 还原的是约数方向；$g(n)=\sum_{n\mid d}f(d)$ 还原的是倍数方向。题目若在 到 上对倍数求和，套错公式会出现 和 对调。

$\varphi(n)=n\sum_{d\mid n}\mu(d)/d$ 里的除法最终是整数。代码请用 sum(mu[d] * (n // d) for d in ...)，不要先把 $\mu(d)/d$ 做成浮点再乘回去。小 $n$ 也许碰巧对，大 会圆整出错。

狄利克雷卷积不交换下标就不成立。$(\mu*g)(n)=\sum_{d\mid n}\mu(d)g(n/d)$，把 $g(n/d)$ 写成 必须同时把 换成 。只改一边，数值会对不上。

$\mu$ 会取负值。前缀和 $M(n)=\sum_{i\le n}\mu(i)$ 在正负之间摆动，不能当正项级数估计。需要界时，用 $|\mu(n)|\le 1$，以及无平方核的密度大约 。

下标从 $0$ 还是从 $1$ 要统一。数组开 n+1 并让 mu[i] 表示 $\mu(i)$，循环从 $2$ 扫到 $n$，这是最不容易错的。若把答案存在 mu[i-1]，后面写 $n/d$ 时非常容易偏一位。

单个数的试除也有对称坑：除掉一个素数 $p$ 后必须立刻检查 $p$ 是否还整除剩下的 $n$。只统计「出现过的素数个数」而不查重指数，会把 $12$ 判成 $\mu(12)=-1$。上面的 mu_single 在第一次除掉 $i$ 后立刻看 n % i，就是为了抓住平方。

无平方因子的计数也是同一套符号。$n$ 无平方因子当且仅当 $\mu(n)\ne 0$，于是 $1$ 到 $N$ 里无平方数的个数可以写成 $\sum_{k=1}^{N}|\mu(k)|$，也可以用容斥写成 。后一个式子里 出现在分母上，正是「每个平方因子被容斥掉一次」。它和 并不矛盾：一个管「约数和是否塌成单位」，一个管「把平方从区间里挖走」。

它在算法里站在哪

容斥数个数、统计互素对、推 $\varphi$ 的前缀、把互素条件收成 $\mu$ 与整除分块，全是同一套：先把条件写成对约数的和，再用 $\mu$ 把和还原成点值。杜教筛能在亚线性时间内求 $\mu$ 和 $\varphi$ 的前缀，底座仍是 $1*\mu=\varepsilon$。

做题时可以按三步走。第一，看题目给的是 $g(n)=\sum_{d\mid n}f(d)$ 还是对倍数求和，先选定反演方向。第二，把指示函数 $[\gcd=1]$ 或 $[n=1]$ 换成 的和，再交换求和顺序，让 走到最外层。第三，内层若出现 ，就整除分块；若只要单个 ，就枚举约数。公式背熟之后，真正耗时的是下标有没有写反。验算时先拿 和素数 代入：这两处项数少，公式写反或者 的符号错了，会立刻露馅。

一次同余管的是单个线性条件有没有解。莫比乌斯管的是对所有约数加起来之后怎么拆回去。两者都是初等数论里会被反复调用的底座。把 $\sum_{d\mid n}\mu(d)=[n=1]$ 记牢，反演就只是换序加这一条恒等式。