如果你学到数论的中后段大概率会在各种题单里撞见同一个名字215题《破译密码》。标准题解里总会挂着“容斥”、“莫比乌斯函数”、“莫比乌斯反演”、“整除分块”四个标签很多同学光看标签就吓退了。其实这道题的代码不过五六十行核心推导也就三步但它确实把数论计数问题里最常用的一套组合拳完整打了一遍。本篇就从零开始拆解这道题说清楚每一步为什么这么做以及实际写代码时哪些细节最容易翻车。1. 题目到底在问什么把“破译密码”翻译成数学语言1.1 从密码背景到计数模型题目套了一个加密相关的故事壳子去除包装后核心问题非常朴素给定三个正整数 (a)、(b)、(d)求满足[ 1 \le x \le a, \quad 1 \le y \le b, \quad \gcd(x, y) d ]的整数对 ((x, y)) 有多少个。注意这里的 (x)、(y) 都是普通正整数范围是闭区间。别小看这个条件——(\gcd(x,y)d) 意味着 (d) 必须同时整除 (x) 和 (y)而且 (x/d) 与 (y/d) 之间不能有大于 1 的公因子。这个“不能有公因子”的限制恰恰就是整个题目的难点所在。如果直接暴力两重循环枚举 (x) 和 (y)每次求一次最大公约数复杂度是 (O(ab))。题目给的是多组查询每组查询的 (a,b) 可以到几万甚至几十万暴力完全活不过样例。所以必须从数论层面找一个能批量计算的表达式。1.2 等价变形把“gcd等于 d”改成“gcd等于 1”遇到 (\gcd(x,y)d)第一个常规操作是缩放。令[ x \frac{x}{d}, \quad y \frac{y}{d} ]则原条件变成[ 1 \le x \le \left\lfloor \frac{a}{d} \right\rfloor, \quad 1 \le y \le \left\lfloor \frac{b}{d} \right\rfloor, \quad \gcd(x, y) 1 ]记[ A \left\lfloor \frac{a}{d} \right\rfloor, \quad B \left\lfloor \frac{b}{d} \right\rfloor ]原问题就等价于在 (1 \le x \le A)、(1 \le y \le B) 的范围内统计互质点对数量。这一步的价值非常大——“互质”条件正好可以被莫比乌斯函数展开而“等于某个数 d”的判定很难直接套数论函数。这个等价模型还有一个很直观的几何角度如果把 ((x, y)) 看成二维网格里的一个格点那么 (\gcd(x,y)1) 意味着这个格点和原点连线的线段上除了两端点外没有其它整数格点。换句话说统计的是“从原点看过去直接可见”的格点数量。2. 莫比乌斯函数到底是个什么函数2.1 定义与核心性质莫比乌斯函数 (\mu(n)) 的定义并不复杂它的取值只有三种情况(\mu(1) 1)如果 (n) 含有平方因子也就是存在某个素数 (p) 满足 (p^2 \mid n)那么 (\mu(n) 0)否则 (n) 可以分解为 (k) 个互不相同的素数的乘积那么 (\mu(n) (-1)^k)。举几个例子就清楚了(\mu(6)1)因为 (62 \times 3) 是两个不同素数相乘(\mu(30)-1)因为 (302\times3\times5) 是三个不同素数相乘(\mu(8)0)因为 (82^3) 里面有平方因子 (2^2)。这个看似奇怪的函数之所以能成为数论里的“开关”是因为它有一个核心性质[ \sum_{d \mid n} \mu(d) \begin{cases} 1, n 1 \ 0, n 1 \end{cases} ]这个式子为什么成立可以把 (n) 的素因子集合记作 (S)。由于当 (d) 含平方因子时 (\mu(d)0)所以求和只需要考虑那些不含平方因子且整除 (n) 的 (d)。这些 (d) 恰好对应着 (S) 的所有子集。于是[ \sum_{d \mid n} \mu(d) \sum_{T \subseteq S} (-1)^{|T|} ]这不就是最经典的容斥公式吗当集合非空时所有子集的符号求和正好抵消结果为 0只有空集对应 (n1) 时结果是 1。所以莫比乌斯函数本质上是一套定义在整个整数集上的“容斥系数”。这也是标题里把“容斥”放在最前面的原因——你马上要做的操作其实就是在对整个自然数集合做一次无穷层的容斥。2.2 用线性筛预处理好 (\mu(1)) 到 (\mu(N))竞赛里通常需要一次性预处理出若干项 (\mu) 值。最常用的方法是线性筛因为 (\mu) 是一个积性函数而且线性筛可以保证每个合数只被它的最小质因子筛一次整体复杂度是 (O(N))。筛法核心逻辑就三条遍历到某个数 (i) 时如果它没有被筛过说明它是质数(\mu(i)-1)用质数 (p) 去筛 (i \times p) 时如果 (i % p 0)说明 (i \times p) 里面包含 (p^2)因此 (\mu(i \times p)0)如果 (i % p ! 0)说明 (i) 和 (p) 互质那么 (\mu(i \times p) -\mu(i))。第三条的负号很关键。(i) 本身如果有 (k) 个不同素因子乘上一个新的不同素数后变成 (k1) 个符号自然要取反如果乘积里出现平方因子直接归零这也是为什么一旦 (i%p0) 就 break——后面的倍数都会继承平方因子用不着继续筛了。具体代码放在第四节完整实现里一起看。3. 核心推导从 (\gcd(x,y)d) 到 (O(\sqrt n)) 查询3.1 用莫比乌斯函数展开互质条件现在目标是求[ \text{ans} \sum_{x1}^{A} \sum_{y1}^{B} [\gcd(x, y) 1] ]这里的方括号是艾弗森约定里面的条件成立时值为 1否则为 0。利用上一节的性质可以把这个判断条件变成一个求和式。因为 (\sum_{d \mid n} \mu(d)) 只有在 (n1) 时才等于 1所以令 (n \gcd(x,y))就有[ [\gcd(x,y)1] \sum_{k \mid \gcd(x,y)} \mu(k) ]所谓 (k \mid \gcd(x,y))其实就是 (k) 同时整除 (x) 和 (y)。于是[ \text{ans} \sum_{x1}^{A} \sum_{y1}^{B} \sum_{k \mid x, , k \mid y} \mu(k) ]3.2 交换求和顺序得到关键单重求和三成循环直接算依然是 (O(A \times B))但我们可以换一个枚举顺序先枚举 (k)再枚举所有能被 (k) 整除的 (x) 和 (y)。对于固定的 (k)在 (1) 到 (A) 范围内能被 (k) 整除的 (x) 有 (\lfloor A/k \rfloor) 个在 (1) 到 (B) 范围内能被 (k) 整除的 (y) 有 (\lfloor B/k \rfloor) 个。两者两两组合就贡献了[ \mu(k) \times \left\lfloor \frac{A}{k} \right\rfloor \times \left\lfloor \frac{B}{k} \right\rfloor ]个合法点对。所以[ \text{ans} \sum_{k1}^{\min(A,B)} \mu(k) \left\lfloor \frac{A}{k} \right\rfloor \left\lfloor \frac{B}{k} \right\rfloor ]到这里问题已经从“二重循环 gcd 判定”变成了“一重求和 整除取整”。这一步就是莫比乌斯反演最常见的落地形态。有人可能会问这就是莫比乌斯反演吗严格地说这里用到的是莫比乌斯反演中“(\phi) 与 (\mu) 的卷积关系”这一核心结论的一种直接应用。竞赛里最常见的用法就是这种把互质条件 ([\gcd(i,j)1]) 用 (\sum_{d \mid \gcd(i,j)} \mu(d)) 展开再交换求和顺序。3.3 整除分块把 (O(\min(A,B))) 降到 (O(\sqrt A \sqrt B))现在式子已经能直接算了复杂度 (O(\min(A,B)))。但多组查询下还是太慢必须继续压。观察 (\lfloor A/k \rfloor)当 (k) 取遍 (1) 到 (A) 时这个函数变化得很“慢”。它只有大约 (2\sqrt A) 个不同的取值。(\lfloor B/k \rfloor) 同理。那么在某个区间 ([l, r]) 内如果[ \left\lfloor \frac{A}{k} \right\rfloor \quad \text{和} \quad \left\lfloor \frac{B}{k} \right\rfloor ]都不变就可以把这段区间内的 (\mu(k)) 先求和再统一乘上这两个常量。这就是整除分块。关键是右端点 (r) 怎么取。对于单独的函数 (\lfloor A/k \rfloor)已知从 (l) 开始它的值保持为 (\lfloor A/l \rfloor)直到 (k) 超过[ \left\lfloor \frac{A}{\lfloor A/l \rfloor} \right\rfloor ]为止。同理对于 (\lfloor B/k \rfloor)保持为 (\lfloor B/l \rfloor) 的右端点是[ \left\lfloor \frac{B}{\lfloor B/l \rfloor} \right\rfloor ]两个函数要同时保持不变右端点显然应该取两者的更小值[ r \min\left( \left\lfloor \frac{A}{\lfloor A/l \rfloor} \right\rfloor, \left\lfloor \frac{B}{\lfloor B/l \rfloor} \right\rfloor \right) ]在这个区间内[ \left\lfloor \frac{A}{k} \right\rfloor \frac{A}{l}, \quad \left\lfloor \frac{B}{k} \right\rfloor \frac{B}{l} ]都是常数。于是区间贡献为[ \left( \sum_{kl}^{r} \mu(k) \right) \times \left\lfloor \frac{A}{l} \right\rfloor \times \left\lfloor \frac{B}{l} \right\rfloor ]前面那个 (\mu) 的区间和用前缀和相减就能 (O(1)) 拿到。每次循环结束后令 (l r 1) 进入下一段。总的段数是 (O(\sqrt A \sqrt B))单次查询就这样从 (O(\min(A,B))) 优化到了 (O(\sqrt A \sqrt B))。3.4 用容斥的视角再理解一遍如果你对“莫比乌斯反演”这个名字感到抽象可以用容斥的语言重新描述整个过程一开始把 (A \times B) 个点对全部算进去。但这些点对里有很多的 (\gcd) 并不是 1比如那些 (x,y) 同时被 2 整除的点对它们的最大公约数至少是 2必须排除。于是减去所有被 2 整除的情况。同理还要减去被 3 整除的情况、被 5 整除的情况……可是问题来了如果一个点对既被 2 整除又被 3 整除那它在减去 2 的那轮和减去 3 的那轮里被减了两次多减了一次需要加回来一次。这个“加回来”的操作就是容斥里的 ()。而被 2、3、5 同时整除的点对加减过程中又会被多算还需要再减……你会发现这套“先全算再逐层修正”的加减系数恰好就是 (\mu(k)) 的取值单个素数贡献 (-1)两个不同素数乘积贡献 (1)三个不同素数乘积贡献 (-1)含平方因子的贡献 (0)。所以莫比乌斯函数本身就可以理解成“整数集合上的容斥系数”。标题里那四个词“容斥 莫比乌斯函数 分块 莫比乌斯反演”正是这个解法里层层递进的四个工具。4. 完整实现AC 代码与复杂度分析4.1 完整代码下面给出可直接提交的 C 实现。#include bits/stdc.h using namespace std; const int MAXN 50005; int mu[MAXN]; int primes[MAXN], tot; long long sumMu[MAXN]; bool isComp[MAXN]; void initMobius(int n) { mu[1] 1; for (int i 2; i n; i) { if (!isComp[i]) { primes[tot] i; mu[i] -1; } for (int j 0; j tot 1LL * i * primes[j] n; j) { isComp[i * primes[j]] true; if (i % primes[j] 0) { mu[i * primes[j]] 0; break; } else { mu[i * primes[j]] -mu[i]; } } } sumMu[0] 0; for (int i 1; i n; i) { sumMu[i] sumMu[i-1] mu[i]; } } long long solveQuery(int a, int b) { if (a 0 || b 0) return 0; int n min(a, b); long long ans 0; for (int l 1, r; l n; l r 1) { r min(a / (a / l), b / (b / l)); ans (sumMu[r] - sumMu[l-1]) * 1LL * (a / l) * (b / l); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin T; initMobius(MAXN - 1); while (T--) { int a, b, d; cin a b d; a / d; b / d; cout solveQuery(a, b) \n; } return 0; }4.2 逐步解释关键行initMobius里mu[1] 1是绝对必须的一行。少了它后面所有乘法都会出错因为 (\mu(1)) 对应的是 (k1) 那一段也就是“互质点对”里最基础的全量计数。线性筛里的i % primes[j] 0分支是保证复杂度为 (O(n)) 的关键。一旦进入这个分支mu[i * primes[j]] 0后必须break否则同一个合数会被多次筛到复杂度退化而且 (\mu) 值也会被覆盖成错误结果。solveQuery里有一个很容易踩的坑忘记对a和b做a / d; b / d。我在初学时就犯过这个错把缩放操作放在solveQuery内部只做了一次样例都过了但提交后大数据全错。正确做法是在读入后立刻缩放让solveQuery只负责统计互质点对。分块循环里l r 1的推进方式也要留意。如果写成l复杂度会打回 (O(\min(A,B)))多组数据直接超时。而r的计算必须同时考虑a和b只取其中一个会导致另一边的整除函数在段内变化贡献计算错误。4.3 复杂度分析预处理部分线性筛本身是 (O(N))其中 (N) 是最大统计范围取MAXN-1。前缀和累加也是 (O(N))。查询部分一次查询的分块段数是 (O(\sqrt A \sqrt B))。每段做常数次整数除法和一次前缀和相减所以单次查询 (O(\sqrt A \sqrt B))。总复杂度为[ O\left(N T(\sqrt A \sqrt B)\right) ]当 (N50000)、(T) 也为 (5 \times 10^4) 级别时这个复杂度在时限内毫无压力。空间方面mu数组和isComp数组各不到 200KBsumMu数组约 400KB总计不足 1MB非常轻量。5. 实战排查常见坑与调试记录5.1 一个本地验证用的手算样例写任何数论题我都建议先准备一个手算样例做基准。比如取 (a6, b6, d1)直接枚举所有 ((x,y))总共有 36 个点对其中互质的点对可以列出来((1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,3),(2,5),(3,1),(3,2),(3,4),(3,5),(4,1),(4,3),(4,5),(5,1),(5,2),(5,3),(5,4),(5,6),(6,1),(6,5))共 23 对。如果你的程序在solveQuery(6, 6)输出不是 23那就可以确定问题出在 (\mu) 的预处理或者分块边界上。这个 23 的数字也可以配合暴力程序做随机对拍。5.2 高频问题速查表症状原因修法样例不过答案整体偏小读入后忘了执行a / d; b / d必须在调用查询函数前完成缩放答案偏大且明显不对mu[1]没有初始化为 1初始化函数开头必须写mu[1] 1部分数据 WA段内贡献算错分块右端点只考虑了a或只考虑了b写成min(a/(a/l), b/(b/l))大数据越界或结果异常中间乘积使用了int使用long long累加和相乘提交超时写成了l或每次查询都for (k1; kn; k)改成l r 1并确保分块循环结构正确多组数据之间结果错乱全局数组未正确初始化或初始化函数调用位置不对在预处理函数里统一初始化且只调用一次5.3 分块边界的一个细节推导有些读者可能对r min(a / (a / l), b / (b / l))有疑问为什么不是min(a, b)也不是分别计算两个右端点再相乘单独考虑 (\lfloor a / k \rfloor)。当 (l) 给定时(\lfloor a / l \rfloor v)。我们要找最大的 (r)使得对于所有 (k \in [l, r])都有 (\lfloor a / k \rfloor v)。这个 (r) 正是[ \left\lfloor \frac{a}{v} \right\rfloor ]因为当 (k) 再大一点时(\lfloor a / k \rfloor) 就会变小。用代码写就是a / (a / l)。注意这里因为是整数除法a/(a/l)本身就代表整除后的结果不需要再套一层 floor。同理对 (\lfloor b / k \rfloor)它的右端点是b / (b / l)。两个整除函数的值要同时保持不变当前段的右端点只能取两者中较小的那个。取大值会让至少其中一个函数提前变化贡献计算失败。5.4 一个容易忽略的数组命名问题有些同学的代码里可能有多个数组比如sum、prime等。如果之前写过别的题sum或prime这些名字很容易和标准库或者其它全局变量冲突。我的习惯是给数论相关的数组加前缀比如muArr、sumMu、primeList并且每个数组都在初始化函数里统一处理避免不同题目之间残留数据。5.5 实测中一个很有意思的错误我曾经在本地测试时把MAXN定义成了50000结果a除以d之后正好达到50000预处理只到49999每次查询到k50000时sumMu[50000]读到了未初始化的数据答案偶尔对偶尔错。这个坑非常隐蔽因为它只在边界数据中出现。解决方案是预处理范围比可能用到的最大值大 1 到 10或者在读入所有数据后统计真正的最大值再按最大值预处理好。这道题数据上限通常是 (5\times 10^4)所以定义MAXN 50005就足够。6. 同类变式把莫比乌斯反演用到更多场景把 215 题的代码吃透之后你会发现很多看似更难的题都只是换了一层壳。变式一求 (\gcd(x,y)) 能被某个给定素数 (p) 整除的点对数量。这几乎就是原题把 (a,b) 分别除以 (p) 后统计互质点对即可。如果题目要求的是“最大公约数为一个质数”的点对总数则需要枚举所有质数 (p)然后对每个 (p) 调用一次分块。更高效的做法是预处理一个辅助数组 (g(n))把“枚举质数、再枚举分块”的两层循环合并成一次分块这本质上是做一次狄利克雷卷积。变式二矩形区域查询。比如求 (x \in [x_1,x_2])、(y \in [y_1,y_2]) 中满足 (\gcd(x,y)1) 的点对数量可以用二维前缀和的思想写成四次形如“(1 \le x \le X, 1 \le y \le Y)”的查询。外部套一层容斥内部每次查询再用莫比乌斯反演加整除分块两个工具组合使用非常自然。变式三带权统计。有些题会要求统计 (\sum_{x1}^{a} \sum_{y1}^{b} f(\gcd(x,y)))其中 (f) 是一个积性函数。处理思路是先枚举 (g \gcd(x,y))令 (xx/g, yy/g)于是原式可以改写成对所有互质点对累加 (f) 的某个前缀形式通常也能用莫比乌斯反演转到单一求和再分块。我现在写这类题时脑内基本会按这样一个固定流程走看到 (\gcd) 条件先想 (\mu) 展开看到求和里有 (\lfloor n/k \rfloor)先想整除分块看到多组查询先想前缀和。这个“三步走”的习惯就是从这道题开始养成的。如果你也正好卡在莫比乌斯反演的入门节点上建议不要只抄代码自己把推导写一遍再把分块的 (l,r) 边界手算几组最后故意改错一两处条件看看结果怎么变。这套折腾下来比你连刷十道同类题都有用。