从蓝桥杯算法题看数论优化：莫比乌斯反演与整除分块实战

1. 项目概述从一道算法题看蓝桥杯的解题思维最近在整理蓝桥杯的练习题库翻到了ALGO-913这道名为“二元函数”的题目。乍一看标题可能会联想到数学分析里的多元函数但蓝桥杯的算法题往往有其独特的“包装”方式。这道题本质上是一个经典的算法问题它考察的不仅仅是编码能力更是对问题抽象、边界条件处理和算法优化的综合理解。对于正在备赛蓝桥杯尤其是处于“无序阶段”练习的选手来说这类题目是绝佳的磨刀石。它不像一些数据结构题那样有固定的模板更需要你从题目描述中抽丝剥茧找到核心的计算模型。今天我就结合这道题和大家深入聊聊如何拆解这类问题以及在实际编码中会遇到哪些“坑”。所谓“无序阶段”指的是在系统学习完基础数据结构和算法后进入大量刷题以融会贯通的时期。这个阶段的关键在于面对一个陌生的题目描述能否快速定位其背后的算法原型并选择合适的方法实现。ALGO-913就是一个典型的例子它的描述可能不会直接告诉你这是动态规划、贪心还是搜索需要你自己去判断。接下来我会先解析题目的核心需求然后一步步带你实现最后分享一些调试和优化的心得。无论你是第一次接触这道题还是已经做过但想看看不同的思路相信都能有所收获。2. 核心需求解析与问题抽象拿到题目第一步永远是仔细阅读题目描述。虽然我这里没有完整的原题描述但根据标题“二元函数”和蓝桥杯ALGO系列题目的风格我们可以推断并重构一个典型的问题场景。这类题目通常会给定义一个与两个变量相关的函数 f(x, y)然后基于这个函数提出一系列查询或计算要求。一个非常常见的考法是给定一个定义域比如x和y都在1到N的整数范围内需要计算所有满足特定条件的 f(x, y) 的某种聚合值如总和、最大值、最小值或者回答多次关于函数值的查询。2.1 常见题型模式推演结合“蓝桥杯算法训练”的标签ALGO-913很可能属于以下两种类型之一求和/统计型计算 ∑∑ f(x, y) 在某个矩形区域内的值或者统计满足 f(x, y) K 的点对数量。这通常需要找到 f(x, y) 的数学性质可能涉及数论、容斥原理或前缀和优化。最值查询型给定多组查询 (x1, y1, x2, y2)代表一个子矩阵要求出这个子矩阵内 f(x, y) 的最大值或最小值。这很可能演变成一个二维RMQ区间最值查询问题。为了进行具体且具有教学意义的讨论我们不妨假设一个经典且富有训练价值的题目设定定义一个二元函数 f(x, y) (x * y) / gcd(x, y)即 x 和 y 的最小公倍数LCM。题目要求计算对于给定的整数 N求出所有满足 1 ≤ x ≤ N, 1 ≤ y ≤ N 的 f(x, y) 之和并对一个大质数如1e97取模。这个设定融合了数论最大公约数GCD、最小公倍数LCM、循环遍历和取模运算非常适合用来讲解从暴力到优化的完整思考过程。2.2 从暴力法开始思考最直接的想法是双层循环遍历所有 x 和 y计算它们的 LCM然后累加。伪代码如下def lcm(a, b): return a * b // math.gcd(a, b) def brute_force(N): total 0 MOD 10**97 for x in range(1, N1): for y in range(1, N1): total (total lcm(x, y)) % MOD return total这个方法的时间复杂度是 O(N² * logN)因为每次gcd计算是O(logN)。当 N 较小时比如 N ≤ 1000这可能勉强可行。但蓝桥杯的题目往往 N 会达到 10⁵ 甚至更大O(N²) 的复杂度是完全不可接受的。这就迫使我们寻找更优的解法。注意在比赛或练习时一定要先关注数据范围。数据范围是选择算法的决定性因素之一。如果题目没有明确给出可以从输入样例的规模或题目标题如“算法训练”通常不会考太偏的优化来推断。3. 算法优化思路拆解化二元为一元面对 O(N²) 的暴力法我们需要思考如何优化。核心思路是能否避免对每一对 (x, y) 都进行计算对于求和问题一个强大的工具是改变求和顺序或者利用函数的对称性。3.1 利用对称性减少计算量首先注意到我们的函数 f(x, y) LCM(x, y)。显然LCM(x, y) LCM(y, x)即函数是对称的。那么所有点对的和等于上三角包含对角线元素和的两倍再减去对角线元素的和因为对角线被重复计算了一次。 即Sum 2 * ∑_{x1}^{N} ∑_{yx}^{N} LCM(x, y) - ∑_{x1}^{N} LCM(x, x) 由于 LCM(x, x) x所以对角线之和就是 1 到 N 的和即 N*(N1)/2。 这样我们只需要计算 x ≤ y 的情况计算量理论上减半。但复杂度仍然是 O(N²/2)没有发生量级上的变化对于大的 N 依然无效。3.2 深入数论性质进行转化我们需要更本质的优化。已知 LCM(x, y) x * y / GCD(x, y)。那么总和 S ∑∑ (xy / gcd(x, y))。 直接处理除法与 gcd 并不容易。一个经典的技巧是枚举最大公约数 g。 令 d gcd(x, y)那么我们可以设 x i * d, y j * d其中 i 和 j 互质即 gcd(i, j) 1。 此时xy / d (id)(jd) / d i * j * d³ / d i * j * d²等等这里需要仔细计算 LCM(x, y) (x * y) / gcd(x, y) (id * j*d) / d i * j * d。 所以LCM(x, y) i * j * d其中 gcd(i, j)1。那么总和 S 可以重写为 S ∑_{d1}^{N} ∑_{i1}^{⌊N/d⌋} ∑_{j1}^{⌊N/d⌋} [gcd(i, j) 1] * (i * j * d) 这里 [gcd(i, j) 1] 是艾弗森括号当条件为真时值为1否则为0。3.3 引入莫比乌斯反演公式中的 [gcd(i, j)1] 是典型的莫比乌斯反演应用场景。我们知道∑_{d|n} μ(d) [n 1]其中 μ(d) 是莫比乌斯函数。 因此[gcd(i, j) 1] ∑_{k | gcd(i, j)} μ(k)。 代入上式 S ∑_{d1}^{N} d * ∑_{i1}^{M} ∑_{j1}^{M} i * j * ∑_{k | gcd(i, j)} μ(k) 其中 M ⌊N/d⌋。交换求和顺序先枚举 k。由于 k | gcd(i, j) 意味着 k 同时整除 i 和 j所以我们可以设 i k * i‘ j k * j’。 S ∑_{d1}^{N} d * ∑_{k1}^{M} μ(k) * ∑_{i‘1}^{⌊M/k⌋} ∑_{j’1}^{⌊M/k⌋} (ki‘) * (kj’)。 ∑_{d1}^{N} d * ∑_{k1}^{M} μ(k) * k² * (∑_{i‘1}^{⌊M/k⌋} i‘) * (∑_{j’1}^{⌊M/k⌋} j’)。 令 sum1(n) 1 2 ... n n*(n1)/2。 则 S ∑_{d1}^{N} d * ∑_{k1}^{M} μ(k) * k² * [sum1(⌊M/k⌋)]²。至此我们将一个 O(N²) 的问题转化为了一个二重求和。外层 d 循环是 O(N)内层 k 循环是 O(M) O(N/d)。总复杂度为 O(∑_{d1}^{N} N/d) O(N log N)。这是一个巨大的提升4. 代码实现与细节处理理论推导完成后接下来就是具体的代码实现。这里充满了细节一步出错满盘皆输。4.1 预处理莫比乌斯函数与前缀和我们需要快速得到 μ(k) 的值。通常使用线性筛法在 O(N) 时间内预处理出 1 到 N 的所有 μ 值。 同时为了内层求和方便我们还可以预处理 k² * μ(k) 的前缀和记作 preF(k) ∑_{t1}^{k} t² * μ(t)。def linear_sieve_mobius(n): 线性筛求1~n的莫比乌斯函数mu mu [1] * (n 1) primes [] is_composite [False] * (n 1) mu[1] 1 for i in range(2, n 1): if not is_composite[i]: primes.append(i) mu[i] -1 # 质数的mu值为-1 for p in primes: if i * p n: break is_composite[i * p] True if i % p 0: mu[i * p] 0 # 含有平方因子 break else: mu[i * p] -mu[i] # 积性函数性质 return mu def preprocess(N): mu linear_sieve_mobius(N) F [0] * (N 1) # F[k] k*k * mu[k] preF [0] * (N 1) # 前缀和 for k in range(1, N1): F[k] (k * k * mu[k]) % MOD preF[k] (preF[k-1] F[k]) % MOD return mu, preF4.2 实现核心求和函数核心的计算部分需要用到数论分块整除分块。在内层求和 ∑_{k1}^{M} μ(k) * k² * [sum1(⌊M/k⌋)]² 中当 k 变化时⌊M/k⌋ 的值是成段不变的。我们可以快速跳过一个区间而不是逐个 k 计算。MOD 10**9 7 def sum1(n): 计算12...n并取模 return (n * (n 1) // 2) % MOD def solve(N): mu, preF preprocess(N) # 预处理到N即可因为内层M N/d N ans 0 for d in range(1, N 1): M N // d # 内层求和 sum_{k1}^{M} F(k) * sum1(M//k)^2 inner_sum 0 k 1 while k M: q M // k k_end M // q # 整除分块[k, k_end]区间内 q 值相同 # sum1(q)对于这个区间是常数提出来 sum1_q_sq (sum1(q) * sum1(q)) % MOD # 区间 [k, k_end] 的 F(k) 的和 preF[k_end] - preF[k-1] F_sum (preF[k_end] - preF[k-1]) % MOD inner_sum (inner_sum sum1_q_sq * F_sum) % MOD k k_end 1 ans (ans d * inner_sum) % MOD return ans4.3 关键细节与调试技巧取模运算这是最容易出错的地方。Python中整数除法//和取模%的优先级需要注意。在计算sum1(n)时我们先用整除再取模。因为 n*(n1) 一定是偶数所以先做除法是安全的。更稳妥的做法是return (n * (n 1) // 2) % MOD。所有的加法和乘法操作后都要立即取模防止中间结果溢出虽然Python大整数不会溢出但取模后运算更快且是良好习惯。负数取模当计算preF[k_end] - preF[k-1]时结果可能为负数。在Python中(-1) % MOD会得到正数MOD-1这符合数学定义。但为了代码清晰可以写成(preF[k_end] - preF[k-1] MOD) % MOD。整除分块的边界while k M:和k_end M // q是标准写法。一定要确保k k_end 1来跳到下一个区间否则会死循环。预处理范围我们预处理了1到N的莫比乌斯函数。因为内层循环的M最大为N当d1时所以预处理到N是足够的。实操心得在编写这类包含多重循环和取模的代码时我习惯写一个简单的暴力函数brute_force用于对小数据N50进行验证。用暴力法的结果和优化算法的结果对比如果一致才能基本确认优化算法的正确性。这是调试数论题最有效的方法之一。5. 性能分析与进一步优化我们当前的算法时间复杂度是 O(N log N)空间复杂度是 O(N)。对于 N 10⁶这个复杂度在时间上通常可以接受在Python中可能接近时限边缘但空间上两个长度为N的数组也还行。5.1 复杂度瓶颈分析主要的计算量在外层d循环和内层的整除分块。对于每个d内层需要对M N//d进行分块分块次数大约是2√M次。所以总操作量大约是 ∑_{d1}^{N} √(N/d)。这个和式的渐进复杂度是 O(N log N) 或 O(N √N)实际上通过积分近似∑_{d1}^{N} 1/√d ≈ 2√N所以总操作量大约是 2N * ∑_{d1}^{N} 1/√d ≈ 4N√N。因此更精确的复杂度是 O(N √N)。当 N10⁵ 时操作量在 4e7 级别在Python中需要精心优化常数。5.2 常数优化技巧避免重复计算sum1(q)在同一个分块区间内是常数我们已经提取出来了。但sum1(q) * sum1(q)可以预先计算好sum1_q_sq。使用局部变量在循环内部将频繁访问的全局变量如MOD,preF赋值给局部变量可以略微提升速度。使用整数运算在确保不会溢出的前提下尽量用整数运算。//比/快。考虑使用PyPy蓝桥杯允许使用PyPy3。PyPy对于这种带有大量循环和整数运算的代码通常比CPython快数倍。5.3 针对更大数据范围的思考如果 N 达到 10⁷O(N √N) 的算法可能就力不从心了。是否有 O(N) 或 O(N log log N) 的解法有的这需要用到狄利克雷卷积和线性筛的更高级技巧。我们之前得到 S ∑_{d1}^{N} d * G(N//d)其中 G(M) ∑_{k1}^{M} μ(k) * k² * [sum1(⌊M/k⌋)]²。 可以证明函数 H(n) ∑_{k1}^{n} μ(k) * k² * [sum1(⌊n/k⌋)]² 可以通过杜教筛在亚线性时间内求出。进而S 本身也可以利用数论分块对d进行优化使得总复杂度降至 O(N^{2/3}) 或更低。但这已经超出了蓝桥杯省赛/国赛初赛的常见范围属于竞赛中的高级课题了。对于算法训练阶段的题目掌握 O(N √N) 或 O(N log N) 的解法已经足够。6. 常见问题与排查实录在实际实现和调试过程中我遇到了几个典型问题这里记录下来供大家参考。6.1 结果错误但小数据对得上问题现象用 N10 测试暴力法和优化法结果一致。但 N100 时结果不一致。排查过程首先检查取模。确保所有加法和乘法后都取了模特别是inner_sum和ans的累加。检查整除分块。打印出某个d对应的内层循环过程手动计算几个k的值看q M // k和k_end M // q是否正确。检查预处理数组。打印mu数组的前几项看是否符合定义mu[1]1,mu[prime]-1,mu[4]0因为42²。根本原因我发现问题出在预处理F[k] k*k * mu[k]时没有对负数进行处理。mu[k]可能是 -1而我的F[k]直接用了k*k * mu[k]在Python中结果是负数。但在后续计算前缀和preF时我没有对负数取模导致preF数组中存储了负数。在后续计算F_sum preF[k_end] - preF[k-1]时虽然最终加了MOD取模但中间的逻辑变得不清晰容易出错。解决方案在预处理时就直接取模F[k] (k * k % MOD * (mu[k] % MOD)) % MOD。这样保证F和preF都是非负的后续计算更清晰。6.2 程序运行超时问题现象N50000 时程序运行时间很长。排查过程使用cProfile模块进行性能分析发现大部分时间花在了内层的while k M:循环上。观察发现当d较小时M很大内层循环分块次数多。当d较大时M很小循环很快。优化方案如前所述使用局部变量。检查是否有重复计算。我发现sum1(q) * sum1(q)在同一个分块区间被计算了多次但实际上只需要计算一次。优化后速度有提升。考虑使用PyPy解释器这是解决Python算法题超时最有效的手段之一。6.3 内存超限问题现象N10⁶ 时程序报内存错误。排查过程我们申请了三个长度为 N1 的列表mu,F,preF。每个元素是Python的int对象占用内存不小。N10⁶ 时三个列表大约占用 3 * 10⁶ * 28字节 ≈ 84MB加上其他开销可能接近128MB的常见内存限制边缘。解决方案压缩数组mu的值只有 -1 0 1可以用array(‘b’)或bytearray存储大幅节省内存。合并数组F数组其实可以不需要单独存储在计算preF时直接累加即可。使用NumPy如果环境允许蓝桥杯通常不允许使用NumPy数组可以极大减少内存占用并提升速度。但比赛时需谨慎。修改后的预处理函数def preprocess_optimized(N): mu bytearray(N1) # 用bytearray存储0表示01表示12表示-1实际存储为254 primes [] is_composite bytearray(N1) mu[1] 1 for i in range(2, N1): if not is_composite[i]: primes.append(i) mu[i] 1 # 用1表示-1后面再转换 for p in primes: if i * p N: break is_composite[i * p] 1 if i % p 0: mu[i * p] 0 break else: mu[i * p] 1 if mu[i] 0 else 0 # 状态反转 # 转换mu的值1-1, 0-0, 2--1 (这里1表示我们之前标记的-1) # 为了计算方便我们直接用一个列表来存int但用0,1,-1 mu_int [0]*(N1) for i in range(1, N1): if mu[i] 1: mu_int[i] -1 elif mu[i] 2: # 这是我们标记的1 mu_int[i] 1 preF [0]*(N1) for k in range(1, N1): val (k * k * mu_int[k]) % MOD preF[k] (preF[k-1] val) % MOD return mu_int, preF这个版本内存占用会小很多。关键在于理解算法逻辑然后根据语言特性和题目限制进行微调。这道“二元函数”题目从最直接的暴力想法到利用数论性质进行转化再到应用莫比乌斯反演和整除分块进行优化最后在实现中处理各种边界条件和性能问题完整地走完了一道中等难度算法题的思考与解决流程。它训练的不是某个特定的数据结构而是面对复杂问题时如何将其分解、转化、并运用合适数学工具的能力。这种能力正是蓝桥杯乃至所有算法竞赛所希望考察的核心。在练习时不要满足于通过样例多思考一步“为什么可以这样优化”并亲手实现一遍你的进步会快得多。