1. 先把莫比乌斯函数看明白它其实是个容斥符号莫比乌斯函数、莫比乌斯反演这两个词第一次在题解里撞见的时候很多人第一反应是这名字听着像拓扑学的东西。其实它跟莫比乌斯环没什么关系纯粹是数论里一个专门用来处理恰好等于这类条件的工具。我刚开始刷数论题的时候看到 $\sum_{d|n}\mu(d)[n1]$ 这个式子完全没感觉直到自己手推了三遍才意识到它本质上就是把至少翻译成恰好的容斥系数。这个工具能干什么简单说凡是题目里出现 $\gcd(i,j)1$、$\gcd(i,j)k$、约数个数求和、互质对数统计这类结构莫比乌斯反演基本都能插一脚。它解决的痛点是直接统计恰好等于某个值的情况很难但统计是某个值的倍数的情况往往非常容易反演就是在这两者之间搭桥。适合已经会写线性筛、了解狄利克雷卷积基本概念的读者如果你是刚学数论分块的新手也能看懂前几节但第六节的排查经验可能更有用。1.1 从平方因子说起定义与三条基本性质莫比乌斯函数记作 $\mu(n)$定义非常干脆只分三种情况$\mu(1)1$这是唯一一个需要单独规定的特例如果 $n$ 能被某个质数的平方整除也就是含有平方因子那么 $\mu(n)0$如果 $n$ 是 $k$ 个互不相同的质数相乘那么 $\mu(n)(-1)^k$。拿几个数试一下$\mu(2)-1$$\mu(6)\mu(2\cdot3)1$$\mu(12)0$因为 $122^2\cdot3$ 含平方因子。这个含平方因子就归零的设定非常关键后面筛法里那个mu[i*p]0就是因为这一条。由定义直接能推出一个核心恒等式$\sum_{d|n}\mu(d)$ 当 $n1$ 时等于 1当 $n1$ 时等于 0。这个式子是整套反演的地基我建议你自己用手推一遍 $n12$ 的约数和感受一下正负号怎么两两抵消的。提示$\mu$ 不是积性函数里的随机符号它是完全积性函数经过卷积得到的乘性函数这个区别在推导时会用到。1.2 为什么 μ 是容斥的天然载体假设我要统计 $1$ 到 $n$ 里与 $n$ 互质的数的个数用容斥是这么想的先减掉所有被某个质因子整除的再加回被两个质因子乘积整除的再减掉三个的……这个加减交替的系数恰好就是 $(-1)^k$也就是 $\mu$ 的非零部分。含平方因子的那些组合不会出现在容斥里因为同时被 $p$ 和 $p$ 整除和被 $p$ 整除是同一件事重复了而 $\mu$ 把它们直接归零正好避免了重复计算。所以你可以把 $\mu(d)$ 理解成容斥展开式里 $d$ 这一项的符号只不过它是被写成了一个独立函数的模样。理解到这一层后面看到 $[n1]\sum_{d|n}\mu(d)$ 就不会觉得突兀了——它就是这个容斥符号的聚合形式。1.3 狄利克雷卷积视角下的 μ数论里有个运算叫狄利克雷卷积记作 $(f*g)(n)\sum_{d|n}f(d)g(n/d)$。定义常函数 $\mathbf{1}(n)1$定义单位函数 $\varepsilon(n)[n1]$那么刚才那个恒等式其实就是 $\mu * \mathbf{1}\varepsilon$。这句话的信息量比它看起来大得多它说明 $\mu$ 和 $\mathbf{1}$ 在狄利克雷卷积意义下互为逆元。有了逆元的概念反演的公式就能一步推出来。如果 $Ff*\mathbf{1}$也就是 $F(n)\sum_{d|n}f(d)$两边同时卷积 $\mu$利用 $\mu*\mathbf{1}\varepsilon$立刻得到 $fF*\mu$也就是 $f(n)\sum_{d|n}\mu(d)F(n/d)$。整个过程干净得不像话比用容斥语言描述要省心太多。我个人的习惯是但凡遇到反演题目先在草稿纸上写成卷积形式确认一下谁是 $f$ 谁是 $F$再展开成求和号。2. 筛莫比乌斯函数两种写法与线性筛的细节拆解函数定义清楚了下一步就是在程序里把它预处理出来。$\mu$ 是乘性函数这意味着只要质因数分解式确定值就确定了特别适合用筛法批量求。实际比赛里我基本只用线性筛因为它的复杂度是严格的 $O(n)$而且顺手能把质数表和欧拉函数一起筛出来性价比很高。这一节把两种写法和各自的代价讲清楚顺便把线性筛里容易写错的地方标出来。2.1 埃氏筛的朴素做法与它的代价最直观的做法是枚举每个数 $i$再枚举它的倍数 $j$做类似质因数分解的统计。比较常见的写法是先筛出所有质数然后对每个质数 $p$枚举它的倍数并累加计数最后根据每个数含有几个不同质因子来决定符号同时判断是否有质数的平方能整除它。这种写法思路简单但常数不小而且判断平方因子那一步需要额外开数组或者做除法判断代码容易写脏。在 $n$ 到 $10^6$ 的量级还能接受一旦到 $10^7$ 且多组数据时间就顶不住了。我早期就是用这种写法后来遇到一道 $10^7$ 的题被卡了将近一秒才老老实实换成线性筛。2.2 线性筛的三类分类讨论线性筛的核心是每个合数只被它最小的质因子筛掉一次。设当前枚举到 $i$质数表里取出的最小可用质数是 $p$令 $xi\cdot p$那么只有三种情况需要讨论如果 $p$ 不能整除 $i$说明 $p$ 是 $x$ 的一个新质因子而且 $x$ 里 $p$ 的指数只有 1于是 $\mu(x)-\mu(i)$符号翻转。如果 $p$ 能整除 $i$那么 $x$ 里 $p$ 的指数至少是 2直接 $\mu(x)0$并且此时必须break因为再往后 $p$ 就不是最小质因子了。$i$ 本身是质数时$\mu(i)-1$这是初始情况。这三条覆盖了所有情形逻辑上没有任何遗漏。要注意第 2 条里赋值 0和break是同时发生的两件事很多人只写了 break 忘了赋值结果筛出来的全是 1 和 -1看不出平方因子的存在。2.3 完整模板与顺手筛欧拉函数下面是我平时用的模板顺手把欧拉函数 $\varphi$ 也一起筛了因为很多题目两个都要用const int MAXN 10000005; int mu[MAXN], phi[MAXN], primes[MAXN], cnt; bool comp[MAXN]; void sieve(int n) { mu[1] 1; phi[1] 1; for (int i 2; i n; i) { if (!comp[i]) { primes[cnt] i; mu[i] -1; phi[i] i - 1; } for (int j 0; j cnt i * primes[j] n; j) { int p primes[j]; int x i * p; comp[x] true; if (i % p 0) { mu[x] 0; phi[x] phi[i] * p; break; } else { mu[x] -mu[i]; phi[x] phi[i] * (p - 1); } } } }这里有几个细节值得单独说。mu[1] 1必须显式赋全局数组默认是 0如果你忘了这一句答案会莫名其妙少贡献。循环从 2 开始是因为 1 已经手动处理了。i * primes[j] n这个边界要写在循环条件里写成i * primes[j] MAXN而n是运行时传入的话可能越界。注意i * primes[j]用 int 计算在 $n$ 接近 $2\times10^9$ 时会溢出虽然线性筛本身不会开到这么大但养成用 long long 承接乘积的习惯没坏处。另外如果你只需要 $\mu$ 而不需要 $\varphi$可以把 $\varphi$ 相关行删掉能省一点常数。实测在 $10^7$ 规模下两个函数一起筛和只筛一个的差距大概在 10% 到 20% 之间如果时间卡得紧精简是有意义的。3. 莫比乌斯反演的两种形式与正确使用姿势筛法只是准备工作真正决定能不能做出题的是反演的转化方向。这里有两种形式很多人学的时候记住了公式做题时却不知道该套哪个根源在于没搞清楚已知什么、要求什么。我下面把两种形式各自对应的问题结构讲清楚再给一套判断方向的方法。3.1 约数形式已知约数求和反推单点值约数形式说的是如果已知 $F(n)\sum_{d|n}f(d)$那么 $f(n)\sum_{d|n}\mu(d)F(n/d)$。它的使用场景是我手里有一个按约数聚合的量想还原出单个 $f(n)$。举个数论之外的例子帮你记假设 $f(d)$ 是某天恰好收到 $d$ 封信的概率$F(n)$ 是收到的信数是 $n$ 的约数的概率那从 $F$ 反推 $f$ 就是这套公式在做的事。这种形式在题目里出现得不算多但一旦遇到求第 $n$ 项的精确值这种问法就要往这个方向想。它的推导用卷积语言只有一行但展开成求和号之后需要注意 $n/d$ 这个自变量的位置写代码时别把 $F(n/d)$ 写成 $F(d)$。3.2 倍数形式竞赛里真正高频的那一套倍数形式是如果已知 $F(n)\sum_{n|d}f(d)$那么 $f(n)\sum_{n|d}\mu(d/n)F(d)$。注意这里的求和范围是 $n$ 的倍数而不是 $n$ 的约数。它对应的问题结构是我容易统计是 $n$ 的倍数的那些量但我真正想要的是恰好等于 $n$的量。互质计数就是最典型的例子。$[,\gcd(i,j)1,]$ 这个条件很难直接处理但如果改成$\gcd(i,j)$ 是 $d$ 的倍数条件就变成了$d$ 同时整除 $i$ 和 $j$计数立刻变成 $\lfloor n/d\rfloor\cdot\lfloor m/d\rfloor$非常好算。于是用反演把它转回去$$[,\gcd(i,j)1,]\sum_{d\mid\gcd(i,j)}\mu(d)$$这个式子是整个数论反演题里出现频率最高的一行我见过的绝大多数题目都是它的变体。把它记牢比记抽象的公式有用得多。3.3 反演的方向感怎么判断该往哪边推我总结的判断方法很土但管用先写下你能轻松算出来的那个量把它设成 $F$再写下你想要的那个量把它设成 $f$然后看两者之间是约数关系还是倍数关系。如果 $F$ 是按 $f$ 的约数聚合的走约数形式如果 $F$ 是按 $f$ 的倍数聚合的走倍数形式。方向搞反了公式虽然也能写出来但求和范围是错的跑出来结果必然不对。还有一个更省事的办法直接记住最常用的那条 $\sum_{d|n}\mu(d)[n1]$遇到需要把等于 1翻译成求和的地方直接套不用每次都从 $F$、$f$ 重新推。我大概有八成以上的题目是靠这一条直接解决的剩下的才需要动到完整形式的反演。4. 实战拆解从 [gcd1] 计数到数论分块理论讲完上一道完整的推导。题目是经典款给定 $n,m$求 $\sum_{i1}^{n}\sum_{j1}^{m}[,\gcd(i,j)1,]$。这类题在各大题库里变形极多但骨架完全一致把这一道吃透后面加个权函数、加个求和目标都是同一套流程。4.1 经典题目的完整推导链第一步把互质条件替换成莫比乌斯求和$$\sum_{i1}^{n}\sum_{j1}^{m}\sum_{d\mid\gcd(i,j)}\mu(d)$$第二步交换求和顺序。原来的顺序是先枚举 $i,j$ 再枚举约数现在改成先枚举 $d$再枚举 $i,j$。关键观察是 $d\mid\gcd(i,j)$ 等价于 $d\mid i$ 且 $d\mid j$所以$$\sum_{d1}^{\min(n,m)}\mu(d)\sum_{d\mid i, i\le n}\sum_{d\mid j, j\le m}1$$第三步内层计数直接变成商$i$ 是 $d$ 的倍数且不超过 $n$个数就是 $\lfloor n/d\rfloor$同理 $j$ 那边是 $\lfloor m/d\rfloor$。于是得到最终形式$$\sum_{d1}^{\min(n,m)}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$$到这里如果你有 $\mu$ 的前缀和数组单次查询是 $O(\min(n,m))$ 的。这就是最朴素的版本多组数据时不够用需要第四节的数论分块。4.2 数论分块把 O(n) 压到 O(√n)数论分块利用的性质是$\lfloor n/d\rfloor$ 只有 $O(\sqrt n)$ 种不同的取值。对于当前左端点 $l$令 $v\lfloor n/l\rfloor$那么满足 $\lfloor n/d\rfloorv$ 的最大 $d$ 是 $\lfloor n/v\rfloor$。在本题里有两个商同时在变所以右端点取两者的小值long long solve(int n, int m) { int lim min(n, m); long long ans 0; for (int l 1, r; l lim; l r 1) { int vn n / l, vm m / l; r min(n / vn, m / vm); ans (long long)(sumMu[r] - sumMu[l - 1]) * vn * vm; } return ans; }这里sumMu是 $\mu$ 的前缀和因为分块之后每一段里 $\lfloor n/d\rfloor\lfloor m/d\rfloor$ 是常数只需要乘上这一段 $\mu$ 的和。很多人第一次写会忘记前缀和直接对每个 $d$ 取值再累加那就退化成 $O(n)$ 了。注意右端点计算是min(n / vn, m / vm)不是min(n, m) / vn。这两个写法在不同数据下会给出不同结果后者是错的因为它默认两个商对应的分界点一致。分块版本单次查询复杂度是 $O(\sqrt n\sqrt m)$配合 $O(n)$ 的筛法预处理面对 $10^4$ 组询问、$n$ 到 $10^7$ 的数据能轻松通过。4.3 复杂度账本与数据范围取舍做这类题前先算一笔账能省下很多无谓的尝试。假设筛法上限是 $N$询问组数是 $T$那么总复杂度是 $O(NT\sqrt N)$。拿 $N10^7$、$T10^4$ 代入$T\sqrt N$ 大约是 $3\times10^7$加上筛法的一亿次操作在常规时间内是安全的。但如果 $T$ 到了 $10^5$分块部分就变成 $3\times10^8$这时候要么减少询问次数要么考虑别的路子。我把常见组合整理成表方便你直接对照数据规模单次查询策略是否需要分块备注$N\le 10^5$$T\le 10^3$直接枚举 $d$否暴力足够别过度设计$N\le 10^7$$T\le 10^4$前缀和加分块是最典型的组合$N\le 10^7$$T\le 10^6$分块加预处理商是需要额外的常数优化$N\ge 10^9$杜教筛是见下一节另外$\mu$ 的前缀和会出现在负数区间如果用 int 承接乘积$\lfloor n/d\rfloor\lfloor m/d\rfloor$ 最大可以到 $10^{14}$ 量级必须用 long long。这一点我在比赛里吃过亏答案对了一半排查半天才发现是溢出。5. 进阶当 n 大到 1e10杜教筛怎么接筛法再好也受限于数组大小$n$ 一旦超过 $10^8$开数组就不现实了。这时候题目往往只要求 $\mu$ 的前缀和 $\sum_{i1}^{n}\mu(i)$而不是完整的函数值表。杜教筛就是专门对付这种只要前缀和、但 $n$ 很大的场景配合分块可以做到亚线性。5.1 前缀和问题的瓶颈线性筛要求把 $1$ 到 $n$ 的每个数都过一遍$n10^{10}$ 时这是十亿次以上的操作内存也放不下。但注意我们真正需要的只是前缀和而这个前缀和在分块中只会被用到若干个形如 $\lfloor n/i\rfloor$ 的位置这类位置总共只有 $O(\sqrt n)$ 个。这就意味着不需要算出所有项只需要算出这些关键位置的值杜教筛的切入点就在这里。5.2 杜教筛的推导与实现要点推导思路是从卷积恒等式出发。已知 $\mu * \mathbf{1}\varepsilon$两边取前缀和$$\sum_{i1}^{n}\varepsilon(i)\sum_{i1}^{n}\sum_{d|i}\mu(d)$$左边等于 1因为只有 $i1$ 时 $\varepsilon$ 非零。右边交换求和顺序变成 $\sum_{d1}^{n}\mu(d)\lfloor n/d\rfloor$。把 $d1$ 那一项 $\mu(1)\cdot n$ 拿出来得到$$1\sum_{d1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloorn\cdot S(n)-\sum_{d2}^{n}\sum_{k\le n/d}\mu(k)$$整理后得出递推式 $S(n)1-\sum_{l2}^{n}S(\lfloor n/l\rfloor)$其中内层用数论分块批量计算。递归过程中大量重复访问同一个 $S$ 值所以必须加记忆化。unordered_maplong long, long long memo; long long S(long long n) { if (n MAXN) return sumMu[n]; // 小范围直接查筛好的表 if (memo.count(n)) return memo[n]; long long res 1; for (long long l 2, r; l n; l r 1) { r n / (n / l); res - (r - l 1) * S(n / l); } return memo[n] res; }小范围用线性筛的结果兜底是个关键技巧。如果全部递归常数会大到无法接受通常把阈值设在 $5\times10^6$ 到 $10^7$ 之间实测能明显降低运行时间。5.3 记忆化与哈希表选型记忆化容器有两种常见选择unordered_map和手写的哈希表。unordered_map写起来省事但在 $O(\sqrt n)$ 级别的访问次数下它的常数可能成为瓶颈尤其在需要防构造数据的场合。手写一个开地址法的哈希表或者用gp_hash_table这类扩展容器速度通常能快一倍以上。提示杜教筛的递归深度很浅但每层内部的循环次数不少所以性能瓶颈在哈希查找而不在递归本身。另外要留意数值范围。$S(n)$ 的绝对值不会超过 $n$用long long承接完全够用但如果题目里还有其他乘积项一起算的时候仍然要防溢出。6. 踩坑记录与速查表这一节是我这些年做题、带新人时反复见到的错误整理成表格和条目方便你在卡住的时候快速对照。说实话反演本身的推导不难难的是实现里的各种细节很多想通了却写不对的情况都是这些小地方造成的。6.1 常见错误速查现象可能原因排查方式答案恒为 0 或恒为 1mu[1]未初始化为 1打印前 10 项对照定义结果比预期大很多含平方因子的位置未置 0检查i % p 0分支前缀和出现异常大正数int 溢出改 long long 并重跑小数据分块结果偏小右端点算错用 $n10$ 手算每段区间大范围查询超时未加记忆化或阈值设太小加大线性筛上限多组询问答案漂移前缀和未预处理确认sumMu已提前算好这张表里的每一条我都真实踩过尤其是第一条和第三条属于新手期的固定节目。6.2 对拍与调试的几条实用套路调试数论题最有效的手段是对拍。写一个 $O(n^2)$ 的暴力版本直接双重循环枚举 $i,j$ 判断 $\gcd$然后随机生成小的 $n,m$ 跑几百组逐组比较。这个方法我几乎每道反演题都会用一次因为公式写错之后肉眼检查很难发现但小数据对拍几秒就能暴露问题。第二个套路是打印中间量。把 $\mu$ 的前若干项、前缀和的前若干项、分块时每一段的l、r、vn、vm都打出来看是否符合预期。特别是分块只要区间划分正确剩下的就是套公式不会出错。第三个套路是构造极端数据。$n1$ 或者 $m1$ 时$\min(n,m)1$分块循环只跑一次很多边界问题会在这里暴露。还有 $nm$ 的情况两个商始终相等如果代码里两处逻辑写得不对称这时候就能看出来。6.3 一些容易忽略的细节$\mu$ 的前缀和是有正有负的所以用它去乘一个正数时结果可能为负这是正常的不要看到负数就以为算错了。整体答案理论上非负但如果题目要求取模中间过程出现负数需要及时调整到正区间。还有一点是关于反演式的形式选择。有时候两种形式都能推但其中一种会多出一个 $n/d$ 的变量替换代码里容易写错下标。我的建议是优先选择求和范围更简单的那种哪怕推导多写两步实现上也更稳。关于扩展方向这套工具可以往几个方向走一是处理带权版本比如求 $\sum_{i,j}\gcd(i,j)$这时候换用欧拉函数会更直接但用反演也能推二是处理多个变量的情形三元互质计数就是把求和号从两层扩到三层套路完全一样三是结合杜教筛处理更大的数据范围。任何一个方向只要把这一套骨架吃透剩下的都是体力活。我个人在实际操作中的体会是莫比乌斯反演最值得花时间的地方不是背公式而是把那个容斥符号的直觉建立起来。公式忘了可以现场推只要知道 $\mu$ 是在记录容斥的正负号写出 $\sum_{d|n}\mu(d)[n1]$ 就是自然而然的事。至于实现层面线性筛的模板背熟、前缀和不忘开 long long、分块的右端点公式多敲几遍这三件事做到位绝大多数题目都能顺利过掉。
莫比乌斯反演从线性筛到数论分块与杜教筛实战
1. 先把莫比乌斯函数看明白它其实是个容斥符号莫比乌斯函数、莫比乌斯反演这两个词第一次在题解里撞见的时候很多人第一反应是这名字听着像拓扑学的东西。其实它跟莫比乌斯环没什么关系纯粹是数论里一个专门用来处理恰好等于这类条件的工具。我刚开始刷数论题的时候看到 $\sum_{d|n}\mu(d)[n1]$ 这个式子完全没感觉直到自己手推了三遍才意识到它本质上就是把至少翻译成恰好的容斥系数。这个工具能干什么简单说凡是题目里出现 $\gcd(i,j)1$、$\gcd(i,j)k$、约数个数求和、互质对数统计这类结构莫比乌斯反演基本都能插一脚。它解决的痛点是直接统计恰好等于某个值的情况很难但统计是某个值的倍数的情况往往非常容易反演就是在这两者之间搭桥。适合已经会写线性筛、了解狄利克雷卷积基本概念的读者如果你是刚学数论分块的新手也能看懂前几节但第六节的排查经验可能更有用。1.1 从平方因子说起定义与三条基本性质莫比乌斯函数记作 $\mu(n)$定义非常干脆只分三种情况$\mu(1)1$这是唯一一个需要单独规定的特例如果 $n$ 能被某个质数的平方整除也就是含有平方因子那么 $\mu(n)0$如果 $n$ 是 $k$ 个互不相同的质数相乘那么 $\mu(n)(-1)^k$。拿几个数试一下$\mu(2)-1$$\mu(6)\mu(2\cdot3)1$$\mu(12)0$因为 $122^2\cdot3$ 含平方因子。这个含平方因子就归零的设定非常关键后面筛法里那个mu[i*p]0就是因为这一条。由定义直接能推出一个核心恒等式$\sum_{d|n}\mu(d)$ 当 $n1$ 时等于 1当 $n1$ 时等于 0。这个式子是整套反演的地基我建议你自己用手推一遍 $n12$ 的约数和感受一下正负号怎么两两抵消的。提示$\mu$ 不是积性函数里的随机符号它是完全积性函数经过卷积得到的乘性函数这个区别在推导时会用到。1.2 为什么 μ 是容斥的天然载体假设我要统计 $1$ 到 $n$ 里与 $n$ 互质的数的个数用容斥是这么想的先减掉所有被某个质因子整除的再加回被两个质因子乘积整除的再减掉三个的……这个加减交替的系数恰好就是 $(-1)^k$也就是 $\mu$ 的非零部分。含平方因子的那些组合不会出现在容斥里因为同时被 $p$ 和 $p$ 整除和被 $p$ 整除是同一件事重复了而 $\mu$ 把它们直接归零正好避免了重复计算。所以你可以把 $\mu(d)$ 理解成容斥展开式里 $d$ 这一项的符号只不过它是被写成了一个独立函数的模样。理解到这一层后面看到 $[n1]\sum_{d|n}\mu(d)$ 就不会觉得突兀了——它就是这个容斥符号的聚合形式。1.3 狄利克雷卷积视角下的 μ数论里有个运算叫狄利克雷卷积记作 $(f*g)(n)\sum_{d|n}f(d)g(n/d)$。定义常函数 $\mathbf{1}(n)1$定义单位函数 $\varepsilon(n)[n1]$那么刚才那个恒等式其实就是 $\mu * \mathbf{1}\varepsilon$。这句话的信息量比它看起来大得多它说明 $\mu$ 和 $\mathbf{1}$ 在狄利克雷卷积意义下互为逆元。有了逆元的概念反演的公式就能一步推出来。如果 $Ff*\mathbf{1}$也就是 $F(n)\sum_{d|n}f(d)$两边同时卷积 $\mu$利用 $\mu*\mathbf{1}\varepsilon$立刻得到 $fF*\mu$也就是 $f(n)\sum_{d|n}\mu(d)F(n/d)$。整个过程干净得不像话比用容斥语言描述要省心太多。我个人的习惯是但凡遇到反演题目先在草稿纸上写成卷积形式确认一下谁是 $f$ 谁是 $F$再展开成求和号。2. 筛莫比乌斯函数两种写法与线性筛的细节拆解函数定义清楚了下一步就是在程序里把它预处理出来。$\mu$ 是乘性函数这意味着只要质因数分解式确定值就确定了特别适合用筛法批量求。实际比赛里我基本只用线性筛因为它的复杂度是严格的 $O(n)$而且顺手能把质数表和欧拉函数一起筛出来性价比很高。这一节把两种写法和各自的代价讲清楚顺便把线性筛里容易写错的地方标出来。2.1 埃氏筛的朴素做法与它的代价最直观的做法是枚举每个数 $i$再枚举它的倍数 $j$做类似质因数分解的统计。比较常见的写法是先筛出所有质数然后对每个质数 $p$枚举它的倍数并累加计数最后根据每个数含有几个不同质因子来决定符号同时判断是否有质数的平方能整除它。这种写法思路简单但常数不小而且判断平方因子那一步需要额外开数组或者做除法判断代码容易写脏。在 $n$ 到 $10^6$ 的量级还能接受一旦到 $10^7$ 且多组数据时间就顶不住了。我早期就是用这种写法后来遇到一道 $10^7$ 的题被卡了将近一秒才老老实实换成线性筛。2.2 线性筛的三类分类讨论线性筛的核心是每个合数只被它最小的质因子筛掉一次。设当前枚举到 $i$质数表里取出的最小可用质数是 $p$令 $xi\cdot p$那么只有三种情况需要讨论如果 $p$ 不能整除 $i$说明 $p$ 是 $x$ 的一个新质因子而且 $x$ 里 $p$ 的指数只有 1于是 $\mu(x)-\mu(i)$符号翻转。如果 $p$ 能整除 $i$那么 $x$ 里 $p$ 的指数至少是 2直接 $\mu(x)0$并且此时必须break因为再往后 $p$ 就不是最小质因子了。$i$ 本身是质数时$\mu(i)-1$这是初始情况。这三条覆盖了所有情形逻辑上没有任何遗漏。要注意第 2 条里赋值 0和break是同时发生的两件事很多人只写了 break 忘了赋值结果筛出来的全是 1 和 -1看不出平方因子的存在。2.3 完整模板与顺手筛欧拉函数下面是我平时用的模板顺手把欧拉函数 $\varphi$ 也一起筛了因为很多题目两个都要用const int MAXN 10000005; int mu[MAXN], phi[MAXN], primes[MAXN], cnt; bool comp[MAXN]; void sieve(int n) { mu[1] 1; phi[1] 1; for (int i 2; i n; i) { if (!comp[i]) { primes[cnt] i; mu[i] -1; phi[i] i - 1; } for (int j 0; j cnt i * primes[j] n; j) { int p primes[j]; int x i * p; comp[x] true; if (i % p 0) { mu[x] 0; phi[x] phi[i] * p; break; } else { mu[x] -mu[i]; phi[x] phi[i] * (p - 1); } } } }这里有几个细节值得单独说。mu[1] 1必须显式赋全局数组默认是 0如果你忘了这一句答案会莫名其妙少贡献。循环从 2 开始是因为 1 已经手动处理了。i * primes[j] n这个边界要写在循环条件里写成i * primes[j] MAXN而n是运行时传入的话可能越界。注意i * primes[j]用 int 计算在 $n$ 接近 $2\times10^9$ 时会溢出虽然线性筛本身不会开到这么大但养成用 long long 承接乘积的习惯没坏处。另外如果你只需要 $\mu$ 而不需要 $\varphi$可以把 $\varphi$ 相关行删掉能省一点常数。实测在 $10^7$ 规模下两个函数一起筛和只筛一个的差距大概在 10% 到 20% 之间如果时间卡得紧精简是有意义的。3. 莫比乌斯反演的两种形式与正确使用姿势筛法只是准备工作真正决定能不能做出题的是反演的转化方向。这里有两种形式很多人学的时候记住了公式做题时却不知道该套哪个根源在于没搞清楚已知什么、要求什么。我下面把两种形式各自对应的问题结构讲清楚再给一套判断方向的方法。3.1 约数形式已知约数求和反推单点值约数形式说的是如果已知 $F(n)\sum_{d|n}f(d)$那么 $f(n)\sum_{d|n}\mu(d)F(n/d)$。它的使用场景是我手里有一个按约数聚合的量想还原出单个 $f(n)$。举个数论之外的例子帮你记假设 $f(d)$ 是某天恰好收到 $d$ 封信的概率$F(n)$ 是收到的信数是 $n$ 的约数的概率那从 $F$ 反推 $f$ 就是这套公式在做的事。这种形式在题目里出现得不算多但一旦遇到求第 $n$ 项的精确值这种问法就要往这个方向想。它的推导用卷积语言只有一行但展开成求和号之后需要注意 $n/d$ 这个自变量的位置写代码时别把 $F(n/d)$ 写成 $F(d)$。3.2 倍数形式竞赛里真正高频的那一套倍数形式是如果已知 $F(n)\sum_{n|d}f(d)$那么 $f(n)\sum_{n|d}\mu(d/n)F(d)$。注意这里的求和范围是 $n$ 的倍数而不是 $n$ 的约数。它对应的问题结构是我容易统计是 $n$ 的倍数的那些量但我真正想要的是恰好等于 $n$的量。互质计数就是最典型的例子。$[,\gcd(i,j)1,]$ 这个条件很难直接处理但如果改成$\gcd(i,j)$ 是 $d$ 的倍数条件就变成了$d$ 同时整除 $i$ 和 $j$计数立刻变成 $\lfloor n/d\rfloor\cdot\lfloor m/d\rfloor$非常好算。于是用反演把它转回去$$[,\gcd(i,j)1,]\sum_{d\mid\gcd(i,j)}\mu(d)$$这个式子是整个数论反演题里出现频率最高的一行我见过的绝大多数题目都是它的变体。把它记牢比记抽象的公式有用得多。3.3 反演的方向感怎么判断该往哪边推我总结的判断方法很土但管用先写下你能轻松算出来的那个量把它设成 $F$再写下你想要的那个量把它设成 $f$然后看两者之间是约数关系还是倍数关系。如果 $F$ 是按 $f$ 的约数聚合的走约数形式如果 $F$ 是按 $f$ 的倍数聚合的走倍数形式。方向搞反了公式虽然也能写出来但求和范围是错的跑出来结果必然不对。还有一个更省事的办法直接记住最常用的那条 $\sum_{d|n}\mu(d)[n1]$遇到需要把等于 1翻译成求和的地方直接套不用每次都从 $F$、$f$ 重新推。我大概有八成以上的题目是靠这一条直接解决的剩下的才需要动到完整形式的反演。4. 实战拆解从 [gcd1] 计数到数论分块理论讲完上一道完整的推导。题目是经典款给定 $n,m$求 $\sum_{i1}^{n}\sum_{j1}^{m}[,\gcd(i,j)1,]$。这类题在各大题库里变形极多但骨架完全一致把这一道吃透后面加个权函数、加个求和目标都是同一套流程。4.1 经典题目的完整推导链第一步把互质条件替换成莫比乌斯求和$$\sum_{i1}^{n}\sum_{j1}^{m}\sum_{d\mid\gcd(i,j)}\mu(d)$$第二步交换求和顺序。原来的顺序是先枚举 $i,j$ 再枚举约数现在改成先枚举 $d$再枚举 $i,j$。关键观察是 $d\mid\gcd(i,j)$ 等价于 $d\mid i$ 且 $d\mid j$所以$$\sum_{d1}^{\min(n,m)}\mu(d)\sum_{d\mid i, i\le n}\sum_{d\mid j, j\le m}1$$第三步内层计数直接变成商$i$ 是 $d$ 的倍数且不超过 $n$个数就是 $\lfloor n/d\rfloor$同理 $j$ 那边是 $\lfloor m/d\rfloor$。于是得到最终形式$$\sum_{d1}^{\min(n,m)}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$$到这里如果你有 $\mu$ 的前缀和数组单次查询是 $O(\min(n,m))$ 的。这就是最朴素的版本多组数据时不够用需要第四节的数论分块。4.2 数论分块把 O(n) 压到 O(√n)数论分块利用的性质是$\lfloor n/d\rfloor$ 只有 $O(\sqrt n)$ 种不同的取值。对于当前左端点 $l$令 $v\lfloor n/l\rfloor$那么满足 $\lfloor n/d\rfloorv$ 的最大 $d$ 是 $\lfloor n/v\rfloor$。在本题里有两个商同时在变所以右端点取两者的小值long long solve(int n, int m) { int lim min(n, m); long long ans 0; for (int l 1, r; l lim; l r 1) { int vn n / l, vm m / l; r min(n / vn, m / vm); ans (long long)(sumMu[r] - sumMu[l - 1]) * vn * vm; } return ans; }这里sumMu是 $\mu$ 的前缀和因为分块之后每一段里 $\lfloor n/d\rfloor\lfloor m/d\rfloor$ 是常数只需要乘上这一段 $\mu$ 的和。很多人第一次写会忘记前缀和直接对每个 $d$ 取值再累加那就退化成 $O(n)$ 了。注意右端点计算是min(n / vn, m / vm)不是min(n, m) / vn。这两个写法在不同数据下会给出不同结果后者是错的因为它默认两个商对应的分界点一致。分块版本单次查询复杂度是 $O(\sqrt n\sqrt m)$配合 $O(n)$ 的筛法预处理面对 $10^4$ 组询问、$n$ 到 $10^7$ 的数据能轻松通过。4.3 复杂度账本与数据范围取舍做这类题前先算一笔账能省下很多无谓的尝试。假设筛法上限是 $N$询问组数是 $T$那么总复杂度是 $O(NT\sqrt N)$。拿 $N10^7$、$T10^4$ 代入$T\sqrt N$ 大约是 $3\times10^7$加上筛法的一亿次操作在常规时间内是安全的。但如果 $T$ 到了 $10^5$分块部分就变成 $3\times10^8$这时候要么减少询问次数要么考虑别的路子。我把常见组合整理成表方便你直接对照数据规模单次查询策略是否需要分块备注$N\le 10^5$$T\le 10^3$直接枚举 $d$否暴力足够别过度设计$N\le 10^7$$T\le 10^4$前缀和加分块是最典型的组合$N\le 10^7$$T\le 10^6$分块加预处理商是需要额外的常数优化$N\ge 10^9$杜教筛是见下一节另外$\mu$ 的前缀和会出现在负数区间如果用 int 承接乘积$\lfloor n/d\rfloor\lfloor m/d\rfloor$ 最大可以到 $10^{14}$ 量级必须用 long long。这一点我在比赛里吃过亏答案对了一半排查半天才发现是溢出。5. 进阶当 n 大到 1e10杜教筛怎么接筛法再好也受限于数组大小$n$ 一旦超过 $10^8$开数组就不现实了。这时候题目往往只要求 $\mu$ 的前缀和 $\sum_{i1}^{n}\mu(i)$而不是完整的函数值表。杜教筛就是专门对付这种只要前缀和、但 $n$ 很大的场景配合分块可以做到亚线性。5.1 前缀和问题的瓶颈线性筛要求把 $1$ 到 $n$ 的每个数都过一遍$n10^{10}$ 时这是十亿次以上的操作内存也放不下。但注意我们真正需要的只是前缀和而这个前缀和在分块中只会被用到若干个形如 $\lfloor n/i\rfloor$ 的位置这类位置总共只有 $O(\sqrt n)$ 个。这就意味着不需要算出所有项只需要算出这些关键位置的值杜教筛的切入点就在这里。5.2 杜教筛的推导与实现要点推导思路是从卷积恒等式出发。已知 $\mu * \mathbf{1}\varepsilon$两边取前缀和$$\sum_{i1}^{n}\varepsilon(i)\sum_{i1}^{n}\sum_{d|i}\mu(d)$$左边等于 1因为只有 $i1$ 时 $\varepsilon$ 非零。右边交换求和顺序变成 $\sum_{d1}^{n}\mu(d)\lfloor n/d\rfloor$。把 $d1$ 那一项 $\mu(1)\cdot n$ 拿出来得到$$1\sum_{d1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloorn\cdot S(n)-\sum_{d2}^{n}\sum_{k\le n/d}\mu(k)$$整理后得出递推式 $S(n)1-\sum_{l2}^{n}S(\lfloor n/l\rfloor)$其中内层用数论分块批量计算。递归过程中大量重复访问同一个 $S$ 值所以必须加记忆化。unordered_maplong long, long long memo; long long S(long long n) { if (n MAXN) return sumMu[n]; // 小范围直接查筛好的表 if (memo.count(n)) return memo[n]; long long res 1; for (long long l 2, r; l n; l r 1) { r n / (n / l); res - (r - l 1) * S(n / l); } return memo[n] res; }小范围用线性筛的结果兜底是个关键技巧。如果全部递归常数会大到无法接受通常把阈值设在 $5\times10^6$ 到 $10^7$ 之间实测能明显降低运行时间。5.3 记忆化与哈希表选型记忆化容器有两种常见选择unordered_map和手写的哈希表。unordered_map写起来省事但在 $O(\sqrt n)$ 级别的访问次数下它的常数可能成为瓶颈尤其在需要防构造数据的场合。手写一个开地址法的哈希表或者用gp_hash_table这类扩展容器速度通常能快一倍以上。提示杜教筛的递归深度很浅但每层内部的循环次数不少所以性能瓶颈在哈希查找而不在递归本身。另外要留意数值范围。$S(n)$ 的绝对值不会超过 $n$用long long承接完全够用但如果题目里还有其他乘积项一起算的时候仍然要防溢出。6. 踩坑记录与速查表这一节是我这些年做题、带新人时反复见到的错误整理成表格和条目方便你在卡住的时候快速对照。说实话反演本身的推导不难难的是实现里的各种细节很多想通了却写不对的情况都是这些小地方造成的。6.1 常见错误速查现象可能原因排查方式答案恒为 0 或恒为 1mu[1]未初始化为 1打印前 10 项对照定义结果比预期大很多含平方因子的位置未置 0检查i % p 0分支前缀和出现异常大正数int 溢出改 long long 并重跑小数据分块结果偏小右端点算错用 $n10$ 手算每段区间大范围查询超时未加记忆化或阈值设太小加大线性筛上限多组询问答案漂移前缀和未预处理确认sumMu已提前算好这张表里的每一条我都真实踩过尤其是第一条和第三条属于新手期的固定节目。6.2 对拍与调试的几条实用套路调试数论题最有效的手段是对拍。写一个 $O(n^2)$ 的暴力版本直接双重循环枚举 $i,j$ 判断 $\gcd$然后随机生成小的 $n,m$ 跑几百组逐组比较。这个方法我几乎每道反演题都会用一次因为公式写错之后肉眼检查很难发现但小数据对拍几秒就能暴露问题。第二个套路是打印中间量。把 $\mu$ 的前若干项、前缀和的前若干项、分块时每一段的l、r、vn、vm都打出来看是否符合预期。特别是分块只要区间划分正确剩下的就是套公式不会出错。第三个套路是构造极端数据。$n1$ 或者 $m1$ 时$\min(n,m)1$分块循环只跑一次很多边界问题会在这里暴露。还有 $nm$ 的情况两个商始终相等如果代码里两处逻辑写得不对称这时候就能看出来。6.3 一些容易忽略的细节$\mu$ 的前缀和是有正有负的所以用它去乘一个正数时结果可能为负这是正常的不要看到负数就以为算错了。整体答案理论上非负但如果题目要求取模中间过程出现负数需要及时调整到正区间。还有一点是关于反演式的形式选择。有时候两种形式都能推但其中一种会多出一个 $n/d$ 的变量替换代码里容易写错下标。我的建议是优先选择求和范围更简单的那种哪怕推导多写两步实现上也更稳。关于扩展方向这套工具可以往几个方向走一是处理带权版本比如求 $\sum_{i,j}\gcd(i,j)$这时候换用欧拉函数会更直接但用反演也能推二是处理多个变量的情形三元互质计数就是把求和号从两层扩到三层套路完全一样三是结合杜教筛处理更大的数据范围。任何一个方向只要把这一套骨架吃透剩下的都是体力活。我个人在实际操作中的体会是莫比乌斯反演最值得花时间的地方不是背公式而是把那个容斥符号的直觉建立起来。公式忘了可以现场推只要知道 $\mu$ 是在记录容斥的正负号写出 $\sum_{d|n}\mu(d)[n1]$ 就是自然而然的事。至于实现层面线性筛的模板背熟、前缀和不忘开 long long、分块的右端点公式多敲几遍这三件事做到位绝大多数题目都能顺利过掉。
