第一次在题解区看到 $\sum_{d\mid n}\mu(d)$ 这种写法的时候我是有点抗拒的——一个函数取值只有 $1,-1,0$ 三种凭什么能扛起反演这么大的名头后来刷了一轮 GCD 计数、约数个数和、LCM 求和这几类题才发现莫比乌斯函数本质上就是一套被封装好的容斥系数它把所有恰好等于的问题系统性地转成了至少是倍数的问题。这套思路一旦想通很多原本要推半天的式子可以顺着模板直接写出来。这篇内容适合两类人一类是刚学完埃氏筛、线性筛看到莫比乌斯反演四个字就头皮发麻的算法竞赛新手另一类是会背公式但每次写题都要重新推一遍、经常在整除分块边界上翻车的老选手。整篇从 μ 的取值规律讲起把狄利克雷卷积、线性筛、整除分块、几个经典模型一直到杜教筛入口串成一条线中间穿插我自己在写题和调试时踩过的具体坑。读完之后你应该能做到看到求 $\sum\sum[\gcd(i,j)1]$这类式子不再靠背而是能自己顺着反演的框架推出来。1. 莫比乌斯函数的取值规律从平方因子到容斥系数1.1 定义背后那条容易被忽略的边界先把定义摆清楚因为这决定了后面所有性质的来源。对正整数 $n$莫比乌斯函数 $\mu(n)$ 按下面三条规则取值$\mu(1)1$如果 $n$ 能被某个质数的平方整除也就是含平方因子那么 $\mu(n)0$如果 $n$ 是 $k$ 个互不相同的质数的乘积那么 $\mu(n)(-1)^k$。这里最容易出错的是第一条和第二条的边界。$\mu(1)1$ 不是随便规定的它是为了配合后面那条核心恒等式才被硬性钉死成 1 的而含平方因子就归零这一条是整个函数里唯一一个会让结果变成 0 的分支。很多人初学时会把 $n1$ 也想成0 个质数相乘从而误以为 $\mu(1)(-1)^01$结论虽然碰巧对但推导逻辑是错的——$n1$ 是被单独定义的特例不是从第三条推出来的。1.2 一张表看清 μ 的三种取值光看定义容易迷糊直接列一张表把 1 到 12 的取值摆出来对照就直观得多。$n$质因数分解$\mu(n)$为什么会是这个值1无1特例定义2$2$-11 个奇数次质数$k1$3$3$-1$k1$4$2^2$0含平方因子 $2^2$5$5$-1$k1$6$2\cdot3$1$k2$偶数次7$7$-1$k1$8$2^3$0含平方因子 $2^2$9$3^2$0含平方因子10$2\cdot5$1$k2$11$11$-1$k1$12$2^2\cdot3$0含平方因子从表里能读出一个规律$\mu(n)\ne 0$ 的那些 $n$恰好就是无平方因子数。也就是说$\mu$ 的非零取值范围被压缩得很小凡是有任何质数在 $n$ 里出现两次以上就直接归零。这一点在做前缀和、做分块的时候非常关键因为 $\mu$ 序列里 0 的比例其实相当高。1.3 它为什么天生就是容斥系数把定义放在一边我们换个角度想一个问题要数恰好等于某条件的东西常见手法是容斥。比如求 $1$ 到 $n$ 里与 $n$ 互质的数的个数你会用欧拉函数但要求恰好 gcd 等于某个值的对数就需要一套系统的容斥系数。莫比乌斯函数恰好提供了这套系数。它满足两条很关键的性质第一它是积性函数也就是当 $\gcd(a,b)1$ 时$\mu(ab)\mu(a)\mu(b)$。这条性质让它可以像筛素数那样被线性筛预处理出来。第二它满足下面这条恒等式这条恒等式才是反演的命脉$$\sum_{d\mid n}\mu(d)[n1]$$其中 $[n1]$ 是艾弗森括号当且仅当 $n1$ 时取 1否则取 0。手算验证一下$n6$ 时$\mu(1)\mu(2)\mu(3)\mu(6)1-1-110$$n1$ 时只有一项 $\mu(1)1$。这条式子说明$\mu$ 是一个能把约数求和精确抵消成只在 $n1$ 处留下贡献的工具。换句话说它天然承担了把倍数关系反推回精确相等的任务这就是容斥系数应该干的事。2. μ*1ε反演公式的真正来源2.1 先把狄利克雷卷积的记号统一要讲反演绕不开狄利克雷卷积因为反演本质上是卷积意义下的除法。对两个数论函数 $f,g$它们的狄利克雷卷积定义为$$(f*g)(n)\sum_{d\mid n}f(d),g!\left(\frac{n}{d}\right)$$注意这里的求和遍历的是 $n$ 的约数而不是某个前缀。这个定义和普通的卷积、多项式乘法都不一样它只在约数格上做运算。卷积有三个基本性质交换律 $fggf$、结合律 $(fg)hf(gh)$、以及存在单位元 $\varepsilon$定义为 $\varepsilon(1)1$其余位置都是 0满足 $f*\varepsilonf$。把常函数记作 $\mathbf{1}(n)1$对所有 $n$ 都取 1那么上面那条核心恒等式就可以写成$$\mu*\mathbf{1}\varepsilon$$这就是整篇文章里最重要的一条式子。用文字念出来就是μ 与常函数 1 的狄利克雷卷积等于单位元。你会发现它和普通代数里 $a\cdot a^{-1}1$ 的形式一模一样——也就是说$\mu$ 就是 $\mathbf{1}$ 在卷积意义下的逆元。2.2 用质因数分解证明核心恒等式这条恒等式值得亲手证一遍因为它能顺带解释平方因子归零这条定义的由来。设 $n$ 的质因数分解为 $n\prod p_i^{a_i}$。由于 $\mu$ 是积性函数而 $\mu(d)0$ 当且仅当 $d$ 含平方因子所以对 $\sum_{d\mid n}\mu(d)$ 真正有贡献的 $d$只能是那些每个质因子最多取一次的约数。这样的 $d$ 一共有 $2^{\omega(n)}$ 个其中 $\omega(n)$ 是 $n$ 的不同质因子个数。把这部分贡献单独拎出来设 $n$ 的不同质因子为 $p_1,\dots,p_k$那么$$\sum_{d\mid n}\mu(d)\sum_{S\subseteq{1,\dots,k}}(-1)^{|S|}右边这个求和是一个标准的二项式展开等于 $(1-1)^k$。当 $k\ge 1$ 时它是 0当 $k0$也就是 $n1$时它是 $1$。证完。这个证明同时也告诉我们为什么 $\mu(1)$ 必须等于 1——如果把它设成别的值$n1$ 这一项就对不上了整个恒等式就塌了。2.3 两种形式的反演与它们的适用场合有了 $\mu*\mathbf{1}\varepsilon$反演公式就只是两边同时卷积 $\mu$ 的机械操作。实际题目里常见两种表述形式用途不太一样。约数形式如果 $F(n)\sum_{d\mid n}f(d)$也就是 $Ff*\mathbf{1}$那么两边同时卷 $\mu$ 得到 $fF*\mu$展开就是$$f(n)\sum_{d\mid n}\mu(d),F!\left(\frac{n}{d}\right)\sum_{d\mid n}\mu!\left(\frac{n}{d}\right)F(d)$$这种形式适合条件是关于整除关系的问题比如求恰好 $d$ 是 $n$ 的因子这类结构。倍数形式如果 $F(n)\sum_{n\mid d}f(d)$也就是 $F(n)$ 遍历所有 $n$ 的倍数那么有$$f(n)\sum_{n\mid d}\mu!\left(\frac{d}{n}\right)F(d)$$这种形式在实际做题里出现频率更高因为 gcd、lcm 这类条件天然是倍数方向的。举个例子把 $f(d)$ 定义为gcd 恰好等于 $d$ 的数对数量把 $F(d)$ 定义为$d$ 同时整除两个数的数对数量那么显然 $F(d)\sum_{d\mid k}f(k)$正好是倍数形式。这条路是后面所有 GCD 计数题的通用起点。3. 线性筛求 μO(n) 一次遍历拿到素数表和 μ 值3.1 埃氏筛的存在价值与它的代价$\mu$ 可以暴力求对每个 $n$ 做质因数分解判断有没有平方因子再决定符号。单次复杂度大概是 $O(\sqrt{n})$预处理 $1$ 到 $N$ 就是 $O(N\sqrt N)$$N10^6$ 就已经扛不住了。所以实战里基本都走筛法。有意思的是埃氏筛配合倒着加也能求 $\mu$先把 $\mu$ 数组初始化成 1然后对所有质数 $p$把 $\mu$ 在每个 $p$ 的倍数位置上取反再把每个 $p^2$ 的倍数位置上清零。这个做法总复杂度是 $O(N\log\log N)$代码短容易记在 $N$ 只有 $10^6$ 级别、且对常数不敏感的题目里完全够用。我自己的习惯是只是大概验算思路、写对拍程序时用埃氏筛版本正式提交、且 $N$ 到 $10^7$ 甚至更大时一定换成线性筛。3.2 线性筛分支判断的三种情况线性筛求 $\mu$ 的核心是对每个合数 $i\cdot p$ 分情况讨论其中 $p$ 是当前遍历到的质数$i$ 是从 2 开始递增的枚举变量。三种情况必须分清这是最容易写错的地方。第一种$i$ 是质数。此时 $\mu(i)-1$这是定义直接给的。第二种$i\cdot p$ 中 $p\nmid i$。此时 $p$ 是新加入的质因子且与前 i 的质因子集合不相交所以两者互质由积性直接得 $\mu(i\cdot p)\mu(i)\cdot\mu(p)-\mu(i)$。第三种$i\cdot p$ 中 $p\mid i$。此时 $i\cdot p$ 里 $p$ 至少出现了两次换句话说 $i\cdot p$ 含平方因子所以 $\mu(i\cdot p)0$。更关键的是由于线性筛保证每个合数只被它最小的质因子筛掉一次此时 $p$ 恰好是 $i$ 的最小质因子所以必须break出去不能再继续用更大的质数乘 $i$。这个break条件就是线性筛能做到 $O(N)$ 的原因。3.3 完整模板与几个常见改写把上面三种情况拼起来就是下面这个模板const int MAXN 1e7 5; int mu[MAXN], primes[MAXN / 10], cnt; bool vis[MAXN]; void sieve(int n) { mu[1] 1; for (int i 2; i n; i) { if (!vis[i]) { primes[cnt] i; mu[i] -1; // 情况一i 是质数 } for (int j 1; j cnt 1LL * i * primes[j] n; j) { int p primes[j]; vis[i * p] true; if (i % p 0) { mu[i * p] 0; // 情况三p 已出现含平方因子 break; // 保证每个合数只被最小质因子筛一次 } else { mu[i * p] -mu[i]; // 情况二p 不整除 i积性 } } } }几个实战改写值得提一下。一是把vis换成int类型的minp数组同时记录每个数的最小质因子后面做杜教筛或者分解质因数时会方便很多。二是如果只需要 $\mu$ 的前缀和后面基本上都要可以在筛完之后直接原地做一遍前缀和省一次额外遍历。三是注意1LL * i * primes[j]这个乘法$i$ 和质数都到 $10^7$ 级别时$i\cdot p$ 会超过int范围不转long long会溢出这个坑我踩过一次当时调试了半天以为是筛法逻辑写错了。4. 整除分块把 Σ μ(d)·⌊n/d⌋ 真正算出来的关键4.1 分块为什么成立反演把式子推出来之后通常长这样$\sum_{d1}^{\min(n,m)}\mu(d)\lfloor n/d\rfloor\lfloor m/d\rfloor$。如果对每个 $d$ 都算一遍复杂度是 $O(\min(n,m))$单组询问还行但绝大多数题都是多组询问$10^4$ 组配 $10^5$ 的上界直接就炸了。这时候必须用整除分块把复杂度压到 $O(\sqrt n)$。分块的原理是$\lfloor n/d\rfloor$ 这个值随着 $d$ 增大只会在很少的位置发生跳变。具体来说对固定的 $n$函数 $d\mapsto\lfloor n/d\rfloor$ 的取值只有大约 $2\sqrt n$ 种。更进一步对某个起点 $l$让 $\lfloor n/d\rfloor$ 保持不变的 $d$ 的最大值是 $\left\lfloor \dfrac{n}{\lfloor n/l\rfloor}\right\rfloor$。这个结论是分块的基石理由也不复杂$\lfloor n/d\rfloorq$ 等价于 $q\le n/dq1$也就是 $d\in(\frac{n}{q1},\frac{n}{q}]$这个区间里最大的整数就是 $\lfloor n/q\rfloor$。4.2 结合前缀和的万能模板把分块和 $\mu$ 的前缀和结合就得到了几乎所有这类题的通用骨架。先预处理 $\mathrm{pre}[i]\sum_{j1}^{i}\mu(j)$然后long long solve(int n, int m) { if (n m) swap(n, m); long long ans 0; for (int l 1, r; l n; l r 1) { r min(n / (n / l), m / (m / l)); // 两个函数同时不变的右端点 long long sum_mu pre[r] - pre[l - 1]; ans sum_mu * (n / l) * (m / l); } return ans; }注意这里右端点取的是两个分块右端点的较小值因为要保证 $\lfloor n/d\rfloor$ 和 $\lfloor m/d\rfloor$ 在这一整段区间内都不变。这个写法我建议直接背下来当模板后面所有变体都只是在最内层乘的东西不一样而已——有的题乘的是 $\lfloor n/d\rfloor\lfloor m/d\rfloor$有的题乘的是 $\varphi$ 前缀和有的题乘的是约数个数前缀和。4.3 分块写法里的边界细节分块有几个老生常谈但每次都有人翻车的点。第一循环右端点是 $l$ 而不是 $r$更新语句必须是l r 1写成l r会死循环。第二两个上界不同时一定要先保证n m否则n/(n/l)里的n/l可能为 0虽然大多数情况下写min能兜住但前置交换更省心。第三注意ans的类型哪怕最终题目要求对某个数取模中间累加过程也最好用long long因为 $\sum\mu$ 可能取负值乘上 $\lfloor n/d\rfloor\lfloor m/d\rfloor$ 之后绝对值可能很大。第四如果n比m小很多循环上界写n就够了写m也不会错但多跑一倍时间没有意义。还有一点经验如果题目里出现 $\lfloor n/d\rfloor$ 的奇数次幂或者更高次幂分块依然适用只要保证被乘的因子在分块区间内是常量即可。真正需要放弃分块的情况是内层出现类似 $\lfloor n/(d\cdot k)\rfloor$ 这种除法的复合那时候得换别的套路比如把和式拆成两层枚举。5. 三个必须拿下的经典模型5.1 模型一互质数对计数这是莫比乌斯反演最经典的入门模型。要求 $\sum_{i1}^{n}\sum_{j1}^{m}[\gcd(i,j)1]$。设 $f(d)$ 表示 $\gcd(i,j)d$ 的数对数量$F(d)$ 表示 $d\mid\gcd(i,j)$ 的数对数量。显然 $F(d)\lfloor n/d\rfloor\lfloor m/d\rfloor$而且 $F(d)\sum_{d\mid k}f(k)$是倍数形式所以由反演得 $f(d)\sum_{d\mid k}\mu(k/d)F(k)$。取 $d1$答案就是$$\sum_{k1}^{\min(n,m)}\mu(k)\left\lfloor\frac{n}{k}\right\rfloor\left\lfloor\frac{m}{k}\right\rfloor$$把这个式子和前面的分块模板对照完全对得上。整个推导链条里唯一需要想的地方就是识别出$d\mid\gcd(i,j)$ 且 $d\mid\gcd(i,j)$这个条件是双向含于的一旦这点看通剩下的就是机械替换。我个人的记忆方式是能整除 gcd 的一定能同时整除两个数所以 $F$ 的形式极其简单而反演负责把恰好等于还原出来。5.2 模型二约数个数和的漂亮推导第二类是约数个数和涉及一个很妙的恒等式$$d(ij)\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)1]$$其中 $d(n)$ 表示 $n$ 的约数个数。这个式子的证明值得写下来因为它体现了逐质数独立处理的思想。设 $i\prod p^{a_p}$$j\prod p^{b_p}$那么 $d(ij)\prod_p(a_pb_p1)$。右边对每个质数 $p$ 单独看$x$ 里 $p$ 的指数 $c$ 满足 $0\le c\le a_p$$y$ 里 $p$ 的指数 $e$ 满足 $0\le e\le b_p$而 $\gcd(x,y)1$ 要求对每个 $p$ 不能同时 $c0$ 且 $e0$。于是对单个质数而言合法组合有两类$c0$ 时 $e$ 可以取 $0\dots b_p$共 $b_p1$ 种$e0$ 时 $c$ 可以取 $1\dots a_p$共 $a_p$ 种。加总正好是 $a_pb_p1$ 种。把所有质数乘起来右边就等于 $\prod_p(a_pb_p1)d(ij)$。有了这个恒等式求 $\sum_{i1}^{n}\sum_{j1}^{m}d(ij)$ 就可以把 $[\gcd(x,y)1]$ 用反演展开成 $\sum_{d\mid\gcd(x,y)}\mu(d)$交换求和顺序后得到$$\sum_{d1}^{\min(n,m)}\mu(d)\left(\sum_{x1}^{\lfloor n/d\rfloor}\left\lfloor\frac{n}{dx}\right\rfloor\right)\left(\sum_{y1}^{\lfloor m/d\rfloor}\left\lfloor\frac{m}{dy}\right\rfloor\right)$$括号里那两坨一样的式子其实等于前缀约数个数和 $H(k)\sum_{i1}^{k}d(i)$可以预处理。再套外层分块就能在 $O(\sqrt n)$ 内回答一次询问。这道题典型卡人的地方不在反演而在恒等式的证明和预处理的选择属于反演框架之外的建模难度。5.3 模型三gcd 求和与 lcm 求和第三类是把 $\gcd$ 本身当成求和对象。基础和式是$$\sum_{i1}^{n}\sum_{j1}^{m}\gcd(i,j)$$这里用莫比乌斯反演反而不太顺手更适合直接借用欧拉函数$\gcd(i,j)\sum_{d\mid\gcd(i,j)}\varphi(d)$。于是原式等于$$\sum_{d1}^{\min(n,m)}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$$因为 $d\mid\gcd(i,j)$ 等价于 $d\mid i$ 且 $d\mid j$这样的数对恰好有 $\lfloor n/d\rfloor\lfloor m/d\rfloor$ 个。形式上它和模型一几乎一样只是把 $\mu$ 换成了 $\varphi$预处理也换成 $\varphi$ 的前缀和。所以这两个模型其实可以合在一起记反演出来的求和系数是 μ直接拆 gcd 出来的求和系数是 φ两者都是模板区别只在预处理哪个数组。至于 lcm 求和 $\sum\sum\mathrm{lcm}(i,j)$思路是把 $\mathrm{lcm}(i,j)ij/\gcd(i,j)$ 代进去再用 $\gcd$ 反演但最后会涉及到对 $ij$ 的逐项处理需要额外的技巧比如分别维护 $i$ 的和、$i^2$ 的和等辅助前缀复杂度会上去一档。我一般在遇到带 $ij$ 权重的题目时会先把gcd 恰好为 $d$的对数 $f(d)$ 求出再乘上对应的权重而不是把权值硬塞进反演公式里这样清晰很多。6. 多组询问下的预处理策略与杜教筛入口6.1 离线预处理与前缀和数组大部分莫比乌斯反演题的真实考点其实藏在多组询问这四个字里。单组询问用分块是 $O(\sqrt n)$$10^5$ 组就是 $10^{7.5}$ 级别卡常严重的话过不去。常用的优化是把询问离线排序或者更彻底地改变算法结构。预处理上我一般会一次性把 $\mu$ 筛出来并原地求前缀和同时按需筛出 $\varphi$、约数个数、$H(k)$ 这些辅助数组。注意前缀和的数值范围$\sum_{i1}^{n}\mu(i)$ 的绝对值实际上增长很慢远小于 $n$用int存是安全的但 $\sum\varphi(i)$ 和 $H(k)$ 在 $n10^7$ 时会到 $10^{13}$ 量级必须用long long。这个细节不痛不痒但一旦用错类型表现出来的就是答案莫名变成负数非常难查。另一个实战经验如果题目给的是多组询问且上下界各不相同优先检查能否把询问按某个维度排序后统一处理或者用记忆化把重复的 $\lfloor n/d\rfloor$ 组合缓存起来。很多时候真正的瓶颈不是反演本身而是重复计算。6.2 当 n 到 1e10杜教筛的基本思路如果上界从 $10^7$ 涨到 $10^{10}$ 甚至更大普通的线性筛就开不出数组了这时候要考虑杜教筛。它的核心目标是把 $\mu$ 的前缀和 $S(n)\sum_{i1}^{n}\mu(i)$ 在亚线性时间内算出来。推导思路还是从 $\mu*\mathbf{1}\varepsilon$ 出发。对两边求前缀和$$\sum_{i1}^{n}(\mu*\mathbf{1})(i)\sum_{i1}^{n}\varepsilon(i)1$$左边展开并交换求和顺序$$\sum_{i1}^{n}\sum_{d\mid i}\mu(d)\sum_{d1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor$$把 $\lfloor n/d\rfloor$ 按整除分块分组就可以得到递推式$$S(n)1-\sum_{l2}^{n}S!\left(\left\lfloor\frac{n}{l}\right\rfloor\right)$$这个式子里$l$ 从 2 开始的求和可以分块处理每一块用同一段 $S(\lfloor n/l\rfloor)$。而对于较小的 $\lfloor n/l\rfloor$比如小于某个阈值 $N^{2/3}$可以直接查预先筛好的前缀和表。配合记忆化整体复杂度可以压到 $O(n^{2/3})$ 左右。这里我只把入口讲清楚细节阈值选取、哈希表存取、递归深度属于另一个话题但对于理解反演为什么是基础设施这件事来说看到 $S(n)$ 能被反演恒等式直接导出递推就已经够了。7. 踩过的坑与调试经验7.1 反演方向搞反是最常见的翻车点我见过最多的错误是把$F(n)\sum_{d\mid n}f(d)$和$F(n)\sum_{n\mid d}f(d)$两条式子记混。看似只是约数和倍数的区别实际推导方向完全相反用错了整个答案会变成一个奇怪的、量级都不对的数。判断方法很简单**看 $F$ 的定义里求和变量是$n$ 的约数还是$n$ 的倍数。**如果是约数$\sum_{d\mid n}$反演后把 $\mu$ 卷在约数上如果是倍数$\sum_{n\mid d}$反演后把 $\mu$ 卷在商上。一个更保险的习惯不要死记公式而是每次都从$F$ 是什么和$f$ 是什么这两个定义出发手动写出关系式再套反演。多写两遍之后方向感自然就有了。7.2 分块右端点与溢出分块代码里r min(n / (n / l), m / (m / l))这行如果 $ln$那么n/l会变成 0紧接着除零直接崩。所以循环条件一定是l n且提前保证n m。另一个经典问题是r算出来可能超过n或m——理论上不会但如果 $n$、$m$ 都是unsigned类型中间某一步的减法可能直接翻车所以我一般统一用int或long long不用无符号。溢出的坑我在 3.3 已经提过一次这里再强调线性筛里i * primes[j]别忘了转long long或者至少加个判断否则 $N10^7$ 时 $i\cdot p$ 一旦超过 $2^{31}-1$vis数组就会越界访问有时候不报错、只是结果随机非常难查。7.3 筛法里的几个隐蔽错误最后一个我反复踩的点线性筛里break的位置。写成先算 $\mu$ 再判断i % p 0是对的但如果先判断再赋值会漏掉情况三的mu[i*p] 0。另外vis[i*p] true这行别忘有些变体筛法只求 $\mu$ 不标vis结果就是每个合数被重复筛复杂度退化到 $O(N\log N)$ 甚至更高。还有一个容易被忽视的地方如果只求 $\mu$ 而不需要素数表可以把内层循环写成遍历 $j$ 从 1 到 $n/i$ 再从质数表里取逻辑一样但可读性差一截不建议为了省几行代码牺牲清晰度。真正写题的时候我倾向于保留完整的线性筛结构因为它同时把素数表、$\mu$ 数组、vis标记一次拿全复用到后续任何题目都不会出问题。如果你现在还停留在背公式的阶段我建议换个练法随便拿一道 GCD 计数题先不看题解自己从恰好等于和至少是倍数这两个集合的关系出发写下 $F$ 和 $f$ 的关系然后一步步卷出答案最后再和标准写法对照。大概写过五六道之后你会发现 $\mu$ 那三种取值和两条反演形式根本不用记它们会自动从定义里长出来。
莫比乌斯反演全解：从线性筛、整除分块到杜教筛
第一次在题解区看到 $\sum_{d\mid n}\mu(d)$ 这种写法的时候我是有点抗拒的——一个函数取值只有 $1,-1,0$ 三种凭什么能扛起反演这么大的名头后来刷了一轮 GCD 计数、约数个数和、LCM 求和这几类题才发现莫比乌斯函数本质上就是一套被封装好的容斥系数它把所有恰好等于的问题系统性地转成了至少是倍数的问题。这套思路一旦想通很多原本要推半天的式子可以顺着模板直接写出来。这篇内容适合两类人一类是刚学完埃氏筛、线性筛看到莫比乌斯反演四个字就头皮发麻的算法竞赛新手另一类是会背公式但每次写题都要重新推一遍、经常在整除分块边界上翻车的老选手。整篇从 μ 的取值规律讲起把狄利克雷卷积、线性筛、整除分块、几个经典模型一直到杜教筛入口串成一条线中间穿插我自己在写题和调试时踩过的具体坑。读完之后你应该能做到看到求 $\sum\sum[\gcd(i,j)1]$这类式子不再靠背而是能自己顺着反演的框架推出来。1. 莫比乌斯函数的取值规律从平方因子到容斥系数1.1 定义背后那条容易被忽略的边界先把定义摆清楚因为这决定了后面所有性质的来源。对正整数 $n$莫比乌斯函数 $\mu(n)$ 按下面三条规则取值$\mu(1)1$如果 $n$ 能被某个质数的平方整除也就是含平方因子那么 $\mu(n)0$如果 $n$ 是 $k$ 个互不相同的质数的乘积那么 $\mu(n)(-1)^k$。这里最容易出错的是第一条和第二条的边界。$\mu(1)1$ 不是随便规定的它是为了配合后面那条核心恒等式才被硬性钉死成 1 的而含平方因子就归零这一条是整个函数里唯一一个会让结果变成 0 的分支。很多人初学时会把 $n1$ 也想成0 个质数相乘从而误以为 $\mu(1)(-1)^01$结论虽然碰巧对但推导逻辑是错的——$n1$ 是被单独定义的特例不是从第三条推出来的。1.2 一张表看清 μ 的三种取值光看定义容易迷糊直接列一张表把 1 到 12 的取值摆出来对照就直观得多。$n$质因数分解$\mu(n)$为什么会是这个值1无1特例定义2$2$-11 个奇数次质数$k1$3$3$-1$k1$4$2^2$0含平方因子 $2^2$5$5$-1$k1$6$2\cdot3$1$k2$偶数次7$7$-1$k1$8$2^3$0含平方因子 $2^2$9$3^2$0含平方因子10$2\cdot5$1$k2$11$11$-1$k1$12$2^2\cdot3$0含平方因子从表里能读出一个规律$\mu(n)\ne 0$ 的那些 $n$恰好就是无平方因子数。也就是说$\mu$ 的非零取值范围被压缩得很小凡是有任何质数在 $n$ 里出现两次以上就直接归零。这一点在做前缀和、做分块的时候非常关键因为 $\mu$ 序列里 0 的比例其实相当高。1.3 它为什么天生就是容斥系数把定义放在一边我们换个角度想一个问题要数恰好等于某条件的东西常见手法是容斥。比如求 $1$ 到 $n$ 里与 $n$ 互质的数的个数你会用欧拉函数但要求恰好 gcd 等于某个值的对数就需要一套系统的容斥系数。莫比乌斯函数恰好提供了这套系数。它满足两条很关键的性质第一它是积性函数也就是当 $\gcd(a,b)1$ 时$\mu(ab)\mu(a)\mu(b)$。这条性质让它可以像筛素数那样被线性筛预处理出来。第二它满足下面这条恒等式这条恒等式才是反演的命脉$$\sum_{d\mid n}\mu(d)[n1]$$其中 $[n1]$ 是艾弗森括号当且仅当 $n1$ 时取 1否则取 0。手算验证一下$n6$ 时$\mu(1)\mu(2)\mu(3)\mu(6)1-1-110$$n1$ 时只有一项 $\mu(1)1$。这条式子说明$\mu$ 是一个能把约数求和精确抵消成只在 $n1$ 处留下贡献的工具。换句话说它天然承担了把倍数关系反推回精确相等的任务这就是容斥系数应该干的事。2. μ*1ε反演公式的真正来源2.1 先把狄利克雷卷积的记号统一要讲反演绕不开狄利克雷卷积因为反演本质上是卷积意义下的除法。对两个数论函数 $f,g$它们的狄利克雷卷积定义为$$(f*g)(n)\sum_{d\mid n}f(d),g!\left(\frac{n}{d}\right)$$注意这里的求和遍历的是 $n$ 的约数而不是某个前缀。这个定义和普通的卷积、多项式乘法都不一样它只在约数格上做运算。卷积有三个基本性质交换律 $fggf$、结合律 $(fg)hf(gh)$、以及存在单位元 $\varepsilon$定义为 $\varepsilon(1)1$其余位置都是 0满足 $f*\varepsilonf$。把常函数记作 $\mathbf{1}(n)1$对所有 $n$ 都取 1那么上面那条核心恒等式就可以写成$$\mu*\mathbf{1}\varepsilon$$这就是整篇文章里最重要的一条式子。用文字念出来就是μ 与常函数 1 的狄利克雷卷积等于单位元。你会发现它和普通代数里 $a\cdot a^{-1}1$ 的形式一模一样——也就是说$\mu$ 就是 $\mathbf{1}$ 在卷积意义下的逆元。2.2 用质因数分解证明核心恒等式这条恒等式值得亲手证一遍因为它能顺带解释平方因子归零这条定义的由来。设 $n$ 的质因数分解为 $n\prod p_i^{a_i}$。由于 $\mu$ 是积性函数而 $\mu(d)0$ 当且仅当 $d$ 含平方因子所以对 $\sum_{d\mid n}\mu(d)$ 真正有贡献的 $d$只能是那些每个质因子最多取一次的约数。这样的 $d$ 一共有 $2^{\omega(n)}$ 个其中 $\omega(n)$ 是 $n$ 的不同质因子个数。把这部分贡献单独拎出来设 $n$ 的不同质因子为 $p_1,\dots,p_k$那么$$\sum_{d\mid n}\mu(d)\sum_{S\subseteq{1,\dots,k}}(-1)^{|S|}右边这个求和是一个标准的二项式展开等于 $(1-1)^k$。当 $k\ge 1$ 时它是 0当 $k0$也就是 $n1$时它是 $1$。证完。这个证明同时也告诉我们为什么 $\mu(1)$ 必须等于 1——如果把它设成别的值$n1$ 这一项就对不上了整个恒等式就塌了。2.3 两种形式的反演与它们的适用场合有了 $\mu*\mathbf{1}\varepsilon$反演公式就只是两边同时卷积 $\mu$ 的机械操作。实际题目里常见两种表述形式用途不太一样。约数形式如果 $F(n)\sum_{d\mid n}f(d)$也就是 $Ff*\mathbf{1}$那么两边同时卷 $\mu$ 得到 $fF*\mu$展开就是$$f(n)\sum_{d\mid n}\mu(d),F!\left(\frac{n}{d}\right)\sum_{d\mid n}\mu!\left(\frac{n}{d}\right)F(d)$$这种形式适合条件是关于整除关系的问题比如求恰好 $d$ 是 $n$ 的因子这类结构。倍数形式如果 $F(n)\sum_{n\mid d}f(d)$也就是 $F(n)$ 遍历所有 $n$ 的倍数那么有$$f(n)\sum_{n\mid d}\mu!\left(\frac{d}{n}\right)F(d)$$这种形式在实际做题里出现频率更高因为 gcd、lcm 这类条件天然是倍数方向的。举个例子把 $f(d)$ 定义为gcd 恰好等于 $d$ 的数对数量把 $F(d)$ 定义为$d$ 同时整除两个数的数对数量那么显然 $F(d)\sum_{d\mid k}f(k)$正好是倍数形式。这条路是后面所有 GCD 计数题的通用起点。3. 线性筛求 μO(n) 一次遍历拿到素数表和 μ 值3.1 埃氏筛的存在价值与它的代价$\mu$ 可以暴力求对每个 $n$ 做质因数分解判断有没有平方因子再决定符号。单次复杂度大概是 $O(\sqrt{n})$预处理 $1$ 到 $N$ 就是 $O(N\sqrt N)$$N10^6$ 就已经扛不住了。所以实战里基本都走筛法。有意思的是埃氏筛配合倒着加也能求 $\mu$先把 $\mu$ 数组初始化成 1然后对所有质数 $p$把 $\mu$ 在每个 $p$ 的倍数位置上取反再把每个 $p^2$ 的倍数位置上清零。这个做法总复杂度是 $O(N\log\log N)$代码短容易记在 $N$ 只有 $10^6$ 级别、且对常数不敏感的题目里完全够用。我自己的习惯是只是大概验算思路、写对拍程序时用埃氏筛版本正式提交、且 $N$ 到 $10^7$ 甚至更大时一定换成线性筛。3.2 线性筛分支判断的三种情况线性筛求 $\mu$ 的核心是对每个合数 $i\cdot p$ 分情况讨论其中 $p$ 是当前遍历到的质数$i$ 是从 2 开始递增的枚举变量。三种情况必须分清这是最容易写错的地方。第一种$i$ 是质数。此时 $\mu(i)-1$这是定义直接给的。第二种$i\cdot p$ 中 $p\nmid i$。此时 $p$ 是新加入的质因子且与前 i 的质因子集合不相交所以两者互质由积性直接得 $\mu(i\cdot p)\mu(i)\cdot\mu(p)-\mu(i)$。第三种$i\cdot p$ 中 $p\mid i$。此时 $i\cdot p$ 里 $p$ 至少出现了两次换句话说 $i\cdot p$ 含平方因子所以 $\mu(i\cdot p)0$。更关键的是由于线性筛保证每个合数只被它最小的质因子筛掉一次此时 $p$ 恰好是 $i$ 的最小质因子所以必须break出去不能再继续用更大的质数乘 $i$。这个break条件就是线性筛能做到 $O(N)$ 的原因。3.3 完整模板与几个常见改写把上面三种情况拼起来就是下面这个模板const int MAXN 1e7 5; int mu[MAXN], primes[MAXN / 10], cnt; bool vis[MAXN]; void sieve(int n) { mu[1] 1; for (int i 2; i n; i) { if (!vis[i]) { primes[cnt] i; mu[i] -1; // 情况一i 是质数 } for (int j 1; j cnt 1LL * i * primes[j] n; j) { int p primes[j]; vis[i * p] true; if (i % p 0) { mu[i * p] 0; // 情况三p 已出现含平方因子 break; // 保证每个合数只被最小质因子筛一次 } else { mu[i * p] -mu[i]; // 情况二p 不整除 i积性 } } } }几个实战改写值得提一下。一是把vis换成int类型的minp数组同时记录每个数的最小质因子后面做杜教筛或者分解质因数时会方便很多。二是如果只需要 $\mu$ 的前缀和后面基本上都要可以在筛完之后直接原地做一遍前缀和省一次额外遍历。三是注意1LL * i * primes[j]这个乘法$i$ 和质数都到 $10^7$ 级别时$i\cdot p$ 会超过int范围不转long long会溢出这个坑我踩过一次当时调试了半天以为是筛法逻辑写错了。4. 整除分块把 Σ μ(d)·⌊n/d⌋ 真正算出来的关键4.1 分块为什么成立反演把式子推出来之后通常长这样$\sum_{d1}^{\min(n,m)}\mu(d)\lfloor n/d\rfloor\lfloor m/d\rfloor$。如果对每个 $d$ 都算一遍复杂度是 $O(\min(n,m))$单组询问还行但绝大多数题都是多组询问$10^4$ 组配 $10^5$ 的上界直接就炸了。这时候必须用整除分块把复杂度压到 $O(\sqrt n)$。分块的原理是$\lfloor n/d\rfloor$ 这个值随着 $d$ 增大只会在很少的位置发生跳变。具体来说对固定的 $n$函数 $d\mapsto\lfloor n/d\rfloor$ 的取值只有大约 $2\sqrt n$ 种。更进一步对某个起点 $l$让 $\lfloor n/d\rfloor$ 保持不变的 $d$ 的最大值是 $\left\lfloor \dfrac{n}{\lfloor n/l\rfloor}\right\rfloor$。这个结论是分块的基石理由也不复杂$\lfloor n/d\rfloorq$ 等价于 $q\le n/dq1$也就是 $d\in(\frac{n}{q1},\frac{n}{q}]$这个区间里最大的整数就是 $\lfloor n/q\rfloor$。4.2 结合前缀和的万能模板把分块和 $\mu$ 的前缀和结合就得到了几乎所有这类题的通用骨架。先预处理 $\mathrm{pre}[i]\sum_{j1}^{i}\mu(j)$然后long long solve(int n, int m) { if (n m) swap(n, m); long long ans 0; for (int l 1, r; l n; l r 1) { r min(n / (n / l), m / (m / l)); // 两个函数同时不变的右端点 long long sum_mu pre[r] - pre[l - 1]; ans sum_mu * (n / l) * (m / l); } return ans; }注意这里右端点取的是两个分块右端点的较小值因为要保证 $\lfloor n/d\rfloor$ 和 $\lfloor m/d\rfloor$ 在这一整段区间内都不变。这个写法我建议直接背下来当模板后面所有变体都只是在最内层乘的东西不一样而已——有的题乘的是 $\lfloor n/d\rfloor\lfloor m/d\rfloor$有的题乘的是 $\varphi$ 前缀和有的题乘的是约数个数前缀和。4.3 分块写法里的边界细节分块有几个老生常谈但每次都有人翻车的点。第一循环右端点是 $l$ 而不是 $r$更新语句必须是l r 1写成l r会死循环。第二两个上界不同时一定要先保证n m否则n/(n/l)里的n/l可能为 0虽然大多数情况下写min能兜住但前置交换更省心。第三注意ans的类型哪怕最终题目要求对某个数取模中间累加过程也最好用long long因为 $\sum\mu$ 可能取负值乘上 $\lfloor n/d\rfloor\lfloor m/d\rfloor$ 之后绝对值可能很大。第四如果n比m小很多循环上界写n就够了写m也不会错但多跑一倍时间没有意义。还有一点经验如果题目里出现 $\lfloor n/d\rfloor$ 的奇数次幂或者更高次幂分块依然适用只要保证被乘的因子在分块区间内是常量即可。真正需要放弃分块的情况是内层出现类似 $\lfloor n/(d\cdot k)\rfloor$ 这种除法的复合那时候得换别的套路比如把和式拆成两层枚举。5. 三个必须拿下的经典模型5.1 模型一互质数对计数这是莫比乌斯反演最经典的入门模型。要求 $\sum_{i1}^{n}\sum_{j1}^{m}[\gcd(i,j)1]$。设 $f(d)$ 表示 $\gcd(i,j)d$ 的数对数量$F(d)$ 表示 $d\mid\gcd(i,j)$ 的数对数量。显然 $F(d)\lfloor n/d\rfloor\lfloor m/d\rfloor$而且 $F(d)\sum_{d\mid k}f(k)$是倍数形式所以由反演得 $f(d)\sum_{d\mid k}\mu(k/d)F(k)$。取 $d1$答案就是$$\sum_{k1}^{\min(n,m)}\mu(k)\left\lfloor\frac{n}{k}\right\rfloor\left\lfloor\frac{m}{k}\right\rfloor$$把这个式子和前面的分块模板对照完全对得上。整个推导链条里唯一需要想的地方就是识别出$d\mid\gcd(i,j)$ 且 $d\mid\gcd(i,j)$这个条件是双向含于的一旦这点看通剩下的就是机械替换。我个人的记忆方式是能整除 gcd 的一定能同时整除两个数所以 $F$ 的形式极其简单而反演负责把恰好等于还原出来。5.2 模型二约数个数和的漂亮推导第二类是约数个数和涉及一个很妙的恒等式$$d(ij)\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)1]$$其中 $d(n)$ 表示 $n$ 的约数个数。这个式子的证明值得写下来因为它体现了逐质数独立处理的思想。设 $i\prod p^{a_p}$$j\prod p^{b_p}$那么 $d(ij)\prod_p(a_pb_p1)$。右边对每个质数 $p$ 单独看$x$ 里 $p$ 的指数 $c$ 满足 $0\le c\le a_p$$y$ 里 $p$ 的指数 $e$ 满足 $0\le e\le b_p$而 $\gcd(x,y)1$ 要求对每个 $p$ 不能同时 $c0$ 且 $e0$。于是对单个质数而言合法组合有两类$c0$ 时 $e$ 可以取 $0\dots b_p$共 $b_p1$ 种$e0$ 时 $c$ 可以取 $1\dots a_p$共 $a_p$ 种。加总正好是 $a_pb_p1$ 种。把所有质数乘起来右边就等于 $\prod_p(a_pb_p1)d(ij)$。有了这个恒等式求 $\sum_{i1}^{n}\sum_{j1}^{m}d(ij)$ 就可以把 $[\gcd(x,y)1]$ 用反演展开成 $\sum_{d\mid\gcd(x,y)}\mu(d)$交换求和顺序后得到$$\sum_{d1}^{\min(n,m)}\mu(d)\left(\sum_{x1}^{\lfloor n/d\rfloor}\left\lfloor\frac{n}{dx}\right\rfloor\right)\left(\sum_{y1}^{\lfloor m/d\rfloor}\left\lfloor\frac{m}{dy}\right\rfloor\right)$$括号里那两坨一样的式子其实等于前缀约数个数和 $H(k)\sum_{i1}^{k}d(i)$可以预处理。再套外层分块就能在 $O(\sqrt n)$ 内回答一次询问。这道题典型卡人的地方不在反演而在恒等式的证明和预处理的选择属于反演框架之外的建模难度。5.3 模型三gcd 求和与 lcm 求和第三类是把 $\gcd$ 本身当成求和对象。基础和式是$$\sum_{i1}^{n}\sum_{j1}^{m}\gcd(i,j)$$这里用莫比乌斯反演反而不太顺手更适合直接借用欧拉函数$\gcd(i,j)\sum_{d\mid\gcd(i,j)}\varphi(d)$。于是原式等于$$\sum_{d1}^{\min(n,m)}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$$因为 $d\mid\gcd(i,j)$ 等价于 $d\mid i$ 且 $d\mid j$这样的数对恰好有 $\lfloor n/d\rfloor\lfloor m/d\rfloor$ 个。形式上它和模型一几乎一样只是把 $\mu$ 换成了 $\varphi$预处理也换成 $\varphi$ 的前缀和。所以这两个模型其实可以合在一起记反演出来的求和系数是 μ直接拆 gcd 出来的求和系数是 φ两者都是模板区别只在预处理哪个数组。至于 lcm 求和 $\sum\sum\mathrm{lcm}(i,j)$思路是把 $\mathrm{lcm}(i,j)ij/\gcd(i,j)$ 代进去再用 $\gcd$ 反演但最后会涉及到对 $ij$ 的逐项处理需要额外的技巧比如分别维护 $i$ 的和、$i^2$ 的和等辅助前缀复杂度会上去一档。我一般在遇到带 $ij$ 权重的题目时会先把gcd 恰好为 $d$的对数 $f(d)$ 求出再乘上对应的权重而不是把权值硬塞进反演公式里这样清晰很多。6. 多组询问下的预处理策略与杜教筛入口6.1 离线预处理与前缀和数组大部分莫比乌斯反演题的真实考点其实藏在多组询问这四个字里。单组询问用分块是 $O(\sqrt n)$$10^5$ 组就是 $10^{7.5}$ 级别卡常严重的话过不去。常用的优化是把询问离线排序或者更彻底地改变算法结构。预处理上我一般会一次性把 $\mu$ 筛出来并原地求前缀和同时按需筛出 $\varphi$、约数个数、$H(k)$ 这些辅助数组。注意前缀和的数值范围$\sum_{i1}^{n}\mu(i)$ 的绝对值实际上增长很慢远小于 $n$用int存是安全的但 $\sum\varphi(i)$ 和 $H(k)$ 在 $n10^7$ 时会到 $10^{13}$ 量级必须用long long。这个细节不痛不痒但一旦用错类型表现出来的就是答案莫名变成负数非常难查。另一个实战经验如果题目给的是多组询问且上下界各不相同优先检查能否把询问按某个维度排序后统一处理或者用记忆化把重复的 $\lfloor n/d\rfloor$ 组合缓存起来。很多时候真正的瓶颈不是反演本身而是重复计算。6.2 当 n 到 1e10杜教筛的基本思路如果上界从 $10^7$ 涨到 $10^{10}$ 甚至更大普通的线性筛就开不出数组了这时候要考虑杜教筛。它的核心目标是把 $\mu$ 的前缀和 $S(n)\sum_{i1}^{n}\mu(i)$ 在亚线性时间内算出来。推导思路还是从 $\mu*\mathbf{1}\varepsilon$ 出发。对两边求前缀和$$\sum_{i1}^{n}(\mu*\mathbf{1})(i)\sum_{i1}^{n}\varepsilon(i)1$$左边展开并交换求和顺序$$\sum_{i1}^{n}\sum_{d\mid i}\mu(d)\sum_{d1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor$$把 $\lfloor n/d\rfloor$ 按整除分块分组就可以得到递推式$$S(n)1-\sum_{l2}^{n}S!\left(\left\lfloor\frac{n}{l}\right\rfloor\right)$$这个式子里$l$ 从 2 开始的求和可以分块处理每一块用同一段 $S(\lfloor n/l\rfloor)$。而对于较小的 $\lfloor n/l\rfloor$比如小于某个阈值 $N^{2/3}$可以直接查预先筛好的前缀和表。配合记忆化整体复杂度可以压到 $O(n^{2/3})$ 左右。这里我只把入口讲清楚细节阈值选取、哈希表存取、递归深度属于另一个话题但对于理解反演为什么是基础设施这件事来说看到 $S(n)$ 能被反演恒等式直接导出递推就已经够了。7. 踩过的坑与调试经验7.1 反演方向搞反是最常见的翻车点我见过最多的错误是把$F(n)\sum_{d\mid n}f(d)$和$F(n)\sum_{n\mid d}f(d)$两条式子记混。看似只是约数和倍数的区别实际推导方向完全相反用错了整个答案会变成一个奇怪的、量级都不对的数。判断方法很简单**看 $F$ 的定义里求和变量是$n$ 的约数还是$n$ 的倍数。**如果是约数$\sum_{d\mid n}$反演后把 $\mu$ 卷在约数上如果是倍数$\sum_{n\mid d}$反演后把 $\mu$ 卷在商上。一个更保险的习惯不要死记公式而是每次都从$F$ 是什么和$f$ 是什么这两个定义出发手动写出关系式再套反演。多写两遍之后方向感自然就有了。7.2 分块右端点与溢出分块代码里r min(n / (n / l), m / (m / l))这行如果 $ln$那么n/l会变成 0紧接着除零直接崩。所以循环条件一定是l n且提前保证n m。另一个经典问题是r算出来可能超过n或m——理论上不会但如果 $n$、$m$ 都是unsigned类型中间某一步的减法可能直接翻车所以我一般统一用int或long long不用无符号。溢出的坑我在 3.3 已经提过一次这里再强调线性筛里i * primes[j]别忘了转long long或者至少加个判断否则 $N10^7$ 时 $i\cdot p$ 一旦超过 $2^{31}-1$vis数组就会越界访问有时候不报错、只是结果随机非常难查。7.3 筛法里的几个隐蔽错误最后一个我反复踩的点线性筛里break的位置。写成先算 $\mu$ 再判断i % p 0是对的但如果先判断再赋值会漏掉情况三的mu[i*p] 0。另外vis[i*p] true这行别忘有些变体筛法只求 $\mu$ 不标vis结果就是每个合数被重复筛复杂度退化到 $O(N\log N)$ 甚至更高。还有一个容易被忽视的地方如果只求 $\mu$ 而不需要素数表可以把内层循环写成遍历 $j$ 从 1 到 $n/i$ 再从质数表里取逻辑一样但可读性差一截不建议为了省几行代码牺牲清晰度。真正写题的时候我倾向于保留完整的线性筛结构因为它同时把素数表、$\mu$ 数组、vis标记一次拿全复用到后续任何题目都不会出问题。如果你现在还停留在背公式的阶段我建议换个练法随便拿一道 GCD 计数题先不看题解自己从恰好等于和至少是倍数这两个集合的关系出发写下 $F$ 和 $f$ 的关系然后一步步卷出答案最后再和标准写法对照。大概写过五六道之后你会发现 $\mu$ 那三种取值和两条反演形式根本不用记它们会自动从定义里长出来。
