题号215的《破译密码》在竞赛圈里常被当作莫比乌斯反演的“入门敲门砖”。它表面套了个密码学的壳骨子里却是容斥、莫比乌斯函数、整除分块三件套的组合。如果你刚学完数论基础正需要一道题把莫比乌斯函数、前缀和、分块优化完整串起来这题就是最标准的模板。我不会只抛结论而是从最朴素的枚举出发一步步演到最终的 O(sqrt N) 做法再把预处理、边界处理、对拍调试这些容易踩坑的细节都交代清楚。1. 题目拆解把“破译密码”翻译成数学计数1.1 题目到底在数什么剥掉题目里的背景故事核心要求就一句话给定正整数 a、b、d统计有多少整数对 (x, y)满足 1 ≤ x ≤ a、1 ≤ y ≤ b且 gcd(x, y) d。举个例子。a 4b 6d 2 时肉眼枚举一下x 必须是 2 的倍数可取 2、4y 必须是 2 的倍数可取 2、4、6但不能直接算 2 × 3 6因为 (4, 4) 的 gcd 是 4不是 2。正确的做法是把 x、y 同时除以 d变成统计 gcd(x, y) 1 的数量。x 的范围是 [1, 2]y 的范围是 [1, 3]互质数对有 (1,1)、(1,2)、(1,3)、(2,1)、(2,3)一共 5 对。所以答案是 5。这一步约分非常关键。gcd(x, y) d 当且仅当 x、y 都能被 d 整除并且约掉 d 之后的最大公约数是 1。于是原题等价于设 A floor(a / d)B floor(b / d)求 1 ≤ i ≤ A、1 ≤ j ≤ B 中满足 gcd(i, j) 1 的数对数量。剩下的所有工作都是围绕“统计互质数对”展开的。1.2 为什么三个知识点会凑到一起第一次看到这题很自然会想两层循环枚举 i 和 j复杂度 O(AB)。当 a、b 都到 1e5甚至多组询问时这种做法完全不可行。那能不能换个计数角度统计两数不互质的情况然后从总数里减掉。这就引出了容斥总对数 A × B减去两个数同时是某个质数 p 的倍数的对数再加上同时是两个不同质数倍数的对数……这个容斥过程的每一项权重恰好就是莫比乌斯函数 μ(d)。而枚举公共因子 d 时floor(A / d) 和 floor(B / d) 的值不是随 d 连续变化的。它们在一段区间内保持不变于是可以用整除分块把单次询问从 O(min(A, B)) 压到 O(sqrt(min(A, B)))。所以这不是三个孤立知识点的拼盘而是同一个计数问题化简路径上的自然产物。理解这条路径比单纯背公式有用得多。2. 核心公式推导从 gcd 到莫比乌斯和2.1 一个看似轻巧却极其重要的恒等式对任意正整数 n有[gcd(i, j) 1] Σ_{d | gcd(i, j)} μ(d)这个式子成立的原因是莫比乌斯函数的求和性质当 n 1 时d 只能取 1右边等于 μ(1) 1当 n 1 时n 的所有正因子上的 μ 之和等于 0。第二条性质是莫比乌斯函数的核心。因为 μ(1) 1质数 p 对应 μ(p) -1两个不同质数之积对应 μ 1依次类推。因子求和时选偶数个质数的项和选奇数个质数的项正好抵消只有 n 1 时留下 1。现在把恒等式代入互质数对计数ans Σ_{i1}^{A} Σ_{j1}^{B} [gcd(i, j) 1] Σ_{i1}^{A} Σ_{j1}^{B} Σ_{d | gcd(i, j)} μ(d)交换求和顺序。先枚举 d条件是 d 同时整除 i 和 j。对于固定的 d[1, A] 里 d 的倍数有 floor(A / d) 个[1, B] 里 d 的倍数有 floor(B / d) 个所以贡献是ans Σ_{d1}^{min(A, B)} μ(d) × floor(A / d) × floor(B / d)到这里公式就成型了。剩下的工作就是高效计算这个和。2.2 用容斥视角再解释一遍很多人第一次看到 μ(d) 会觉得抽象其实它就是容斥系数的紧凑写法。想象 A × B 这个全集。我们要留下 gcd 1 的数对去掉所有 gcd 1 的数对。直接去掉“都是 2 的倍数”、“都是 3 的倍数”、“都是 5 的倍数”这些集合后同时被 2、3 两个质数整除的数对被减了两次需要加回来。同理被三个质数同时整除的又加多了需要再减一次。含 1 个质因子系数 -1含 2 个不同质因子系数 1含 3 个不同质因子系数 -1含有平方因子这个数对已经在更小的质因子处被处理过实际上如果 d 含平方因子它在容斥里不该出现因为被“同时是 p² 的倍数”限制的数对早已被“同时是 p 的倍数”的容斥处理干净了μ(d) 0 正好把它剔除。而集合“d | i 且 d | j”的大小正是 floor(A/d) × floor(B/d)。所以最终公式就是一个用 μ 加权、对 d 求和的经典容斥式。2.3 这题和莫比乌斯反演是什么关系严格讲这题没有显式写出反演公式只用到了 μ 的容斥性质和求和恒等式。但它是 gcd 计数问题的原型。常见变体包括求恰好 gcd k 的对数、求区间内互质对数、求约数相关的函数前缀和。这些题在推导到最后都会落到“线性筛预处理一个数论函数并求前缀和然后用整除分块回答询问”的模式上。把这道题的式子亲手推两遍之后学莫比乌斯反演的完整形式会顺很多。反演公式本质上就是“用倍数关系换因数关系”的求和游戏而这题的推导已经把这个核心机制演示了一遍。3. 整除分块把枚举从 O(N) 压到 O(sqrt N)3.1 为什么答案会“分段常数”直接按公式从 d 1 枚举到 min(A, B)单次询问 O(N) 还会超时。优化思路来自向下取整的性质。以 A 100 为例。floor(100 / d) 在 d 1 到 100 之间并不会取 100 个不同值。d 越大商变小并且很多相邻 d 对应的商完全相同。比如 d 34 到 d 50floor(100 / d) 都是 2d 51 到 d 100商都是 1。商相同的区间合起来A / d 只有约 2 * sqrt(A) 种取值。现在式子右边是 floor(A / d) × floor(B / d)乘积相同的区间只会更少。于是我们可以把 d 划分成若干个连续段每一段内两个分式都不变用 μ(d) 在这一段上的和乘以同一个乘积就能得到整段的贡献。3.2 右端点怎么计算已知当前段的左端点是 l令 vA floor(A / l)vB floor(B / l)。我们需要找最大的 r使得 floor(A / r) 仍然等于 vA同时 floor(B / r) 仍然等于 vB。由整除性质能让 floor(A / x) 保持 vA 的最远右端点是 floor(A / vA)。同理B 对应的最远右端点是 floor(B / vB)。两者取较小值r min(floor(A / vA), floor(B / vB))这个 r 就是当前段的右端点。如果 r 超过了 min(A, B)还要再限制一下因为枚举上界就是 min(A, B)。所以一个 for 循环可以写成for (int l 1; l lim; ) { int va A / l; int vb B / l; int r min(A / va, B / vb); r min(r, lim); // 处理 [l, r] 这一段 l r 1; }这就是整除分块的核心写法理解 l 和 r 的跳跃逻辑后根本不需要背模板。3.3 加上前缀和才能 O(1) 取块和每一段的贡献是 (vA × vB) 乘以这段里所有 μ(d) 的和。光有 μ(d) 还不够需要预处理前缀和pre[i] pre[i - 1] mu[i]然后 [l, r] 的 μ 和就是 pre[r] - pre[l - 1]。一次询问里 1 段用一个减法解决整体复杂度 O(sqrt N)。顺带提一句为什么不直接对 μ(d) 这段求和而是用前缀和因为整除分块是一次性把一整段拿走如果段内还一个个加 μ(d)分块就失去意义了。前缀和是分块优化的标配。4. 完整实现线性筛、前缀和与多组询问4.1 线性筛求莫比乌斯函数μ(n) 的定义是μ(1) 1n 含平方因子时 μ(n) 0n 分解为 k 个不同质数乘积时 μ(n) (-1)^k。线性筛可以顺便求出每个数的最小质因子关系从而判断 i * prime[j] 是否含平方因子const int MAXN 100005; int mu[MAXN], pre[MAXN]; int primes[MAXN], cnt; bool vis[MAXN]; void init_mobius(int n) { mu[1] 1; for (int i 2; i n; i) { if (!vis[i]) { primes[cnt] i; mu[i] -1; // 质数只有一个质因子 } for (int j 1; j cnt i * primes[j] n; j) { int v i * primes[j]; vis[v] true; if (i % primes[j] 0) { mu[v] 0; // i 已经含有 primes[j]v 含平方因子 break; } else { mu[v] -mu[i]; // 多一个质因子符号取反 } } } for (int i 1; i n; i) { pre[i] pre[i - 1] mu[i]; } }重点在 i % primes[j] 0 时置 0 并 break。这是一条经典优化保证每个合数只被它的最小质因子筛到一次整体 O(N)。初学的时候很容易漏掉 break虽然结果对但复杂度会退化到 O(N log N)。4.2 查询部分的完整代码预处理完成后每个询问只需要按分块累加long long solve(int a, int b, int d) { int A a / d; int B b / d; if (A 0 || B 0) return 0; int lim min(A, B); long long ans 0; for (int l 1; l lim; ) { int va A / l; int vb B / l; int r min(A / va, B / vb); if (r lim) r lim; int muSum pre[r] - pre[l - 1]; ans 1LL * muSum * va * vb; l r 1; } return ans; }这里有几个细节值得注意答案最大值能到 A × B超过 int 范围必须用 long long。int 型乘法要先乘 1LL防止中间过程溢出。当 d 比 a 或 b 大时A 或 B 可能为 0此时不存在任何满足条件的对直接返回 0。4.3 完整流程与复杂度分析一个多组询问的问题整体流程是读入最大可能值 maxN线性筛预处理 μ 和前缀和读入每组 a、b、d调用 solve输出答案换行。预处理是 O(maxN)单组询问是 O(sqrt(min(A, B)))。如果题目给 1e5 组询问每次 1e5 级别的 sqrt 开销完全顶得住。实际数据中 a、b 可能到 1e7 甚至更大这时 MAXN 需要动态调整而不是定死。提前读入所有询问取 maxN max(a, b) 再预处理能省下不必要的筛法开销。4.4 边界与多组样例的教训我第一次写这题时在 r 的边界上栽过跟头。A 和 B 不对称时A / va 或 B / vb 可能超出 lim。比如 A 100B 3lim 3但 A / (100/3) A / 33 3刚好不超更典型的是 A 100B 5l 1 时 va 100A/va 1vb 5B/vb 1r 1 正常。但 l 稍大后B/vb 会等于 lim1 吗实际上不会大于 lim因为 vb B / l而 l ≤ lim ≤ B所以 vb ≥ 1B / vb ≤ B。但 lim 可能小于 B所以 r min(A/va, B/vb) 可能大于 lim举个例子A 100B 10lim 10l 1 时 r min(1, 1) 1l 10 时 va 10A/va 10vb 1B/vb 10r 10。看起来不会超。但为了保险很多写法仍会写 r min(r, lim)这是无害的。更常见的坑在于 l 更新时写成 l 而不是 l r 1或者 r 计算时用 int 但 va 为 0。l lim 时 va 一定 ≥ 1 吗l ≤ min(A,B) ≤ A所以 A/l ≥ 1没问题。只要 l 不越界va 不会为 0。真正让我踩过的坑反而是多组数据数组没清空。只有 mu[1] 被显式赋值其它位置如果不初始化就累加结果全乱。5. 常见问题与调试心得5.1 小数据对拍验证写完不要急着提交。先用暴力程序对拍。最简单的方式是写一个 O(n^2) 的暴力函数long long brute(int a, int b, int d) { long long res 0; for (int x 1; x a; x) { for (int y 1; y b; y) { if (std::gcd(x, y) d) res; } } return res; }然后随机生成 1000 组 a、b、d范围取 30 以内比较 solve 和暴力结果。全部一致再提交。这一步能筛掉大部分推导和实现错误。5.2 线性筛写错的表现μ 序列前几项是固定的1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0…… 这个序列很有名可以手工打印前 20 项来定位筛法错误。常见的错误有忘记给 mu[1] 赋初值默认是 0导致所有结果偏小在线性筛内层循环里没有 break合数被重复筛到μ 值被多次覆盖判断平方因子写反比如 i % primes[j] ! 0 时才置 0。如果小数据对拍通过但大数据 WA多半是 int 溢出或者 r 端点计算越界多检查 long long 是否到位。5.3 分块写法错误的定位技巧分块的问题很难从小数据看出因为小块边界错误很容易被对拍掩盖。可以用一个对照打印把 solve 里的每一段 [l, r] 输出和暴力逐个枚举时座标对比。如果段端点对不上说明 r 公式写错了。我个人的经验是分块循环里最好写成for (int l 1, r; l lim; l r 1) { r min(A / (A / l), B / (B / l)); if (r lim) r lim; ... }不要省掉 lim 的修正也不要自作聪明地把 min 拆成两个 if那反而容易漏一个。5.4 从这题到莫比乌斯反演进阶这题是所有 gcd 计数题的起点。学会了线性筛 μ 前缀和 整除分块后面刷“求 gcd 恰好为 k 的对数”、约数函数前缀和、狄利克雷卷积初探等题目时会发现套路高度一致写出题目要求的计数式用 [gcd 1] 的 μ 恒等式或反演公式换一种求和顺序得到若干个 floor(n / d) 的乘积之和预处理出需要的数论函数及其前缀和整除分块回答每组询问。区别只在于预处理的对象。有的题要筛 φ有的要筛 μ * id有的要筛 d(n)。线性筛的写法大同小异关键在于理解每个函数在质数幂处的取值以及质因子重复时如何转移。这道《破译密码》看似简单但它把整个莫比乌斯题型的骨架完整训练了一遍。把每一处推导都吃透再遇到同类型题基本就是套模板的熟练工了。