1. 项目概述从一道算法题看数论与组合思维的融合“2021-09-17C. Strange Function(lcm容斥)”这个标题乍一看像是某场编程竞赛很可能是Codeforces的一道题目记录。对于算法竞赛的选手或者对编程和数学感兴趣的朋友来说这背后隐藏的是一道典型的、将数论知识与组合思维深度结合的难题。它考察的远不止是写代码的能力更是对最小公倍数LCM和容斥原理这两个核心数学工具的深刻理解与灵活运用。这道题之所以值得深挖是因为它完美地展示了如何将一个看似复杂的“奇怪函数”计算问题通过数学建模转化为清晰可解的计数问题。如果你正在准备算法竞赛或者想挑战自己的逻辑与数学抽象能力理解这道题的解法会是一次极佳的训练。它不仅教你如何解题更教你一种“化繁为简”的通用思考方式。2. 核心思路拆解为什么是LCM与容斥要理解这道题我们首先得拆解“Strange Function”这个描述。虽然题目原文没有给出但结合“lcm容斥”这个关键提示我们可以推断出题目的典型结构通常这类题目会定义一个函数f(n)它可能与n的某些特定性质的约数、倍数或者不能被某个集合中任何数整除的数有关。而求解的目标往往是计算f(1) f(2) ... f(N)的和或者某个区间内满足f(n) g(n)的n的个数等。2.1 LCM的核心角色定义“步长”与“周期”为什么LCM会出现在这里想象一下如果题目条件与“不能被a或b整除”相关那么“能被a整除”和“能被b整除”的数其出现是有周期的。这个周期正是a和b的最小公倍数 LCM(a, b)。例如考虑所有不能被2或3整除的正整数。数字2的倍数是每2个出现一次3的倍数是每3个出现一次。而同时是2和3的倍数即能被6整除的数它们被重复计算了。这里6就是LCM(2,3)。当我们从总数中减去2的倍数和3的倍数时6的倍数被减了两次所以需要加回来一次。这已经触及了容斥原理的雏形。更复杂的情况是题目条件可能涉及多个数或者与LCM本身直接相关。例如函数f(n)可能被定义为最小的正整数x使得n不能被x整除而这个x又可能与1, 2, 3, ...的LCM序列有关。这时LCM序列L(k) LCM(1, 2, ..., k)的性质就成为解题关键。L(k)增长非常快这允许我们枚举有限的k来处理极大的n。关键思路在算法题中LCM常常用于刻画一组数共同的“影响周期”或“性质边界”。通过枚举这个周期或边界的指数k我们可以将无穷的或大规模的枚举问题转化为对有限个区间的统计问题。2.2 容斥原理的作用处理“或”与“且”的逻辑关系容斥原理是处理集合交并问题的利器。其基本公式对于两个集合A和B是|A ∪ B| |A| |B| - |A ∩ B|。推广到多个集合就是加上所有单个集合大小减去所有两两交集大小加上所有三三交集大小以此类推正负号交替。在这类题目中集合通常被定义为“满足某个条件的数”。例如集合A能被a整除的数。集合B能被b整除的数。 那么“能被a或b整除的数”就是A ∪ B而“既不能被a也不能被b整除的数”就是总数减去|A ∪ B|。当条件变得更复杂比如“不能被1, 2, ..., k中任何一个数整除”我们要求的集合就是所有这些“能被i整除”的集合的并集的补集。直接计算补集大小很困难但计算并集大小可以通过容斥原理来实现。容斥原理将复杂的“或”条件分解为若干个“且”条件的加减组合而“且”条件同时能被若干个数整除对应的集合其大小恰恰可以通过这些数的LCM来方便计算即能被LCM整除的数的个数。2.3 思路融合LCM为容斥提供计算单元至此两者的关系就清晰了问题转化将原问题定义的f(n)或计数条件转化为对一系列集合通常与“整除性”相关的并集或交集的操作。容斥框架使用容斥原理将并集的计算分解为多个子集交集的代数和。LCM计算每一个子集交集例如“同时能被a和b整除的数”其元素个数等于floor(N / LCM(a, b))。这里LCM提供了计算交集大小的直接公式。枚举优化由于LCM增长极快参与容斥的集合通常是1到某个k的整数的子集数量看似是指数级的2^k但实际上当子集的LCM超过上界N时其对结果的贡献为0。因此有效的子集数量是有限的可以通过DFS或位运算枚举来高效实现。3. 典型问题还原与抽象建模虽然我们没有原题但我们可以构建一个与标题描述高度吻合的经典问题模型并给出完整的解决方案。这是算法竞赛中一种常见的题型。假设题目如下定义函数f(n)为最小的正整数k使得n不能被k整除。例如f(1) 2因为1能被1整除但不能被2整除f(2) 32能被1和2整除但不能被3整除f(6) 46能被1,2,3整除但不能被4整除。 给定一个整数N求f(1) f(2) ... f(N)的和。3.1 问题分析与观察首先我们暴力计算小范围的f(n)来寻找规律n1: 除数1(可), 2(不可) - f2n2: 除数1,2(可), 3(不可) - f3n3: 除数1,2,3(可), 4(不可) - f4n4: 除数1,2,3,4(可), 5(不可) - f5n5: 除数1,2,3,4,5(可), 6(不可) - f6n6: 除数1,2,3(可), 4(不可) - f4我们发现对于大多数数f(n)似乎等于n1但n6就是一个反例。f(6)4因为6能被1,2,3整除但不能被4整除。那么n在什么情况下f(n) ! n1呢当存在一个小于n1的数k使得n能被所有小于k的正整数整除但不能被k整除时f(n)就会小于n1。这引出了一个关键概念如果一个数n能被1, 2, ..., k中的所有数整除那么n一定是它们的最小公倍数L(k) LCM(1,2,...,k)的倍数。换句话说n是L(k)的倍数是n能被1..k整除的充要条件。因此我们可以重新描述f(n)找到最大的k使得n是L(k)的倍数。那么f(n) k1。因为n能被1..k整除但不能被k1整除否则k就不是最大的。3.2 数学模型建立设L(k) LCM(1, 2, ..., k)。序列如下L(1)1, L(2)2, L(3)6, L(4)12, L(5)60, L(6)60, L(7)420, L(8)840, L(9)2520, L(10)2520, L(11)27720, L(12)27720, L(13)360360, L(14)360360, L(15)360360, L(16)720720, L(17)12252240, ... 可以看到L(k)增长非常迅速。对于给定的nf(n) k1其中k是满足L(k)整除n的最大整数。 那么求和S(N) Σ_{n1}^{N} f(n)可以转化为按k来分类计数。如何转化考虑所有满足f(n) m的n。根据定义这意味着n能被L(m-1)整除因为k m-1是最大的。n不能被L(m)整除否则k至少是m。因此f(n) m当且仅当n属于集合{ n | L(m-1) | n 且 L(m) ∤ n }。 这个集合可以表示为A {n: L(m-1)的倍数} \ {n: L(m)的倍数}。 而L(m)一定是L(m-1)的倍数因为L(m) LCM(L(m-1), m)所以{n: L(m)的倍数}是{n: L(m-1)的倍数}的子集。于是满足f(n)m的n的个数为count(m) floor(N / L(m-1)) - floor(N / L(m))。3.3 引入容斥原理上面的推导已经很清晰了似乎不需要容斥其实这正是容斥原理最简单形式两个集合的差的应用。我们把它写得更形式化一点设集合U为[1, N]的所有整数。 设集合A {ninU|L(m-1)整除n}。 设集合B {ninU|L(m)整除n}。 我们知道B ⊆ A。 那么我们想要的集合CA \ BA ∩ (U \ B)。 根据容斥原理|C| |A| - |A ∩ B|。由于B ⊆ A所以A ∩ B B。 因此|C| |A| - |B| floor(N/L(m-1)) - floor(N/L(m))。这与我们之前的推导一致。对于更复杂的原始问题可能不是求f(n)的和而是求满足f(n) g(n)的n的个数容斥原理可能会以更复杂的形式出现例如需要处理多个不等式条件的交集。3.4 求和计算现在总和S(N) Σ_{n1}^{N} f(n) Σ_{m} m * count(m)其中m从2开始因为f(n)最小为2。 但是m可以到无穷大吗不。因为当L(m-1) N时floor(N / L(m-1)) 0count(m)为0。所以m只需要枚举到满足L(m-1) N的最大值即可。由于L(k)增长极快m的范围非常小对于N高达1e16m通常也不超过几十。因此算法步骤如下预处理计算出L(k)序列直到L(k) N。对于m从2开始计算count(m) N // L(m-1) - N // L(m)。注意这里//表示整数除法向下取整。L(1)定义为1以保证m2时L(m-1)L(1)1N//1 N。累加m * count(m)到答案中。还需要考虑边界对于那些f(n) m_max1的数即能被L(m_max)整除的数我们的公式中count(m_max1) N//L(m_max) - N//L(m_max1)而L(m_max1) N所以N//L(m_max1)0。因此count(m_max1) N//L(m_max)。这正好对应了所有能被最大L(k)整除的n它们的f(n)确实都是m_max1。计算示例N6预处理 L: L(1)1, L(2)2, L(3)6, L(4)126所以 m_max 3因为 L(3)66。m2: count 6//L(1) - 6//L(2) 6//1 - 6//2 6 - 3 3。贡献2 * 3 6。 对应 n1,3,5f值均为2m3: count 6//L(2) - 6//L(3) 6//2 - 6//6 3 - 1 2。贡献3 * 2 6。 对应 n2,4f值均为3m4: count 6//L(3) - 6//L(4) 6//6 - 6//12 1 - 0 1。贡献4 * 1 4。 对应 n6f值为4总和 S 6 6 4 16。 手动验证f(1)f(2)f(3)f(4)f(5)f(6)23456424等等这里出错了。我们手动算一下f(1)2, f(2)3, f(3)4, f(4)5, f(5)6, f(6)4。和是23456424。我们的算法算出16显然不对。问题出在哪里我们的推导f(n) k1中k是满足L(k)整除n的最大整数。对于 n3L(1)1整除3L(2)2不整除3所以 k1f(3)2但实际 f(3)4。矛盾仔细检查定义f(n)是最小的正整数k使得n不能被k整除。 对于 n3:k1: 3能被1整除。k2: 3不能被2整除是的3除以2余1。所以最小的 k 就是2。 但根据我们之前的计算f(3)应该是2而不是4。我最初举例时写错了纠正f(3)2, f(4)3, f(5)2, f(6)4。 重新计算f(1)2, f(2)3, f(3)2, f(4)3, f(5)2, f(6)4。和为23232416。这与我们算法计算的结果一致所以我们的模型和算法是正确的。这个错误恰恰说明了理解定义的重要性。f(n)是最小的k使得n不能被k整除而不是“最大的k使得n能被1..k整除再加一”。后者是另一种常见函数定义有时称为g(n)。我们的算法实际上解决的是我们重新正确定义的这个问题。4. 算法实现与细节剖析基于上述数学模型我们可以给出高效的算法实现。这里以计算S(N)为例N可以非常大比如1e16。4.1 预处理LCM序列这是算法的关键步骤。我们需要计算L(k) LCM(1, 2, ..., k)。直接循环计算LCM会很快溢出即使使用大整数L(k)的增长也使得我们只需要计算很少的几项。计算L(k)时可以利用性质L(k) L(k-1) * (k / gcd(L(k-1), k))。但更需要注意的是溢出问题。由于我们只关心L(k) N的项当计算过程中L(k)即将超过N时我们可以提前终止。并且由于我们只需要L(k)的值来进行除法N // L(k)当L(k) N时这个除法结果为0我们可以用一个特殊值如N1或0来表示“无穷大”并在计算中判断。实现要点使用64位无符号整数如C的unsigned long long或语言自带的大整数类型如Python的int。在计算L(k)时每次乘法后立即检查是否超过N。如果超过可以标记该L(k)为N并停止后续计算因为后续的L(k)只会更大。存储两个数组lcm[k]存储L(k)的值或标记为N以及一个布尔数组表示是否有效。def preprocess_lcm_until(N): lcm_list [1] # index 0 占位lcm_list[i] 表示 L(i) k 1 current_lcm 1 while True: # 计算 L(k) LCM(current_lcm, k) # 使用 math.gcd 计算最大公约数 import math g math.gcd(current_lcm, k) # 先做除法防止中间溢出 temp current_lcm // g # 检查乘法是否会导致结果超过 N if temp N // k: # 等价于 if temp * k N: # 超过 N后续的 L(k) 都会超过 N停止预处理 break current_lcm temp * k lcm_list.append(current_lcm) k 1 return lcm_list # 示例N10^9 N 10**9 lcm_seq preprocess_lcm_until(N) print(f预处理得到的 L(k) 序列 (直到 {N}): {lcm_seq}) print(f最大的 k 使得 L(k) {N} 是: {len(lcm_seq)-1})4.2 核心求和计算得到lcm_seq后求和计算就非常直接了。注意索引对应关系lcm_seq[i]对应L(i)。def calculate_S(N): lcm_seq preprocess_lcm_until(N) # lcm_seq[0] L(0) 我们定义为1但通常从 L(1) 开始用。这里调整一下。 # 更清晰的写法让 lcm_seq[k] 直接表示 L(k) # 我们预处理时 lcm_list[0]1 (L(1)?)不我们让索引对齐lcm_seq[1] L(1)1 # 但为了计算方便我们通常使用 lcm_seq 作为列表lcm_seq[m] 表示 L(m) # 根据预处理函数lcm_list[0]L(1)1, lcm_list[1]L(2)2, ... # 我们令 lcm_seq[m] L(m)则需要将预处理结果前插一个 L(0)1根据定义L(0)可视为1。 # 实际上在公式 count(m) N//L(m-1) - N//L(m) 中m 从2开始需要 L(1)。 # 简单起见我们构建一个数组 L其中 L[i] 表示 L(i) L [1] # L[0] 1 (方便索引但不用) L.extend(lcm_seq) # 现在 L[1] 1, L[2] 2, L[3] 6, ... # 但我们的预处理结果 lcm_seq 第一个元素已经是 L(1)1所以直接使用它作为 L[1:] # 调整preprocess_lcm_until 返回的列表第一个是 L(1)我们把它当作 L[1] L [0] lcm_seq # L[1] lcm_seq[0], L[2] lcm_seq[1], ... ans 0 M len(L) - 1 # 最大的有效索引L[M] N, L[M1] N 或不存在 for m in range(2, M2): # m 从2到 M1 L_m_1 L[m-1] # L(m-1) # 计算 L(m)如果 m M则 L[m] 有效否则视为无穷大N L_m L[m] if m M else (N 1) # 用 N1 表示 N这样 N // (N1) 0 count_m N // L_m_1 - N // L_m ans m * count_m return ans4.3 复杂度分析时间复杂度预处理 LCM 序列的复杂度为 O(K)其中 K 是满足L(K) N的最大整数。由于L(k)增长超指数级K 非常小。对于N高达10^16K 大约在 40-50 左右。求和循环也是 O(K)。因此总时间复杂度是 O(K)对于任何合理的 N 都是常数时间。空间复杂度O(K)用于存储 LCM 序列。这效率极高完全能够处理极限大的N。5. 容斥原理的更一般化应用场景在我们这个问题中容斥原理的应用相对简单两个集合的差。但在许多其他“Strange Function”类题目中容斥可能需要处理更多集合。典型场景扩展假设问题变为计算1到N中有多少个数n满足f(n) g(n)其中g(n)是另一个函数。 解题步骤往往如下将条件f(n) g(n)分解。通常f(n)和g(n)都可以表示为基于n的整除性质的函数。固定f(n)的可能取值。例如f(n)可能取值2, 3, 4, ...对应n是L(1), L(2), ...的倍数但不是L(2), L(3), ...的倍数。对于每个固定的f(n) m条件f(n) g(n)转化为g(n) m。而g(n)往往也可以根据n的因子情况确定一个值。此时我们需要统计满足以下两个条件的n的个数 a)n是L(m-1)的倍数但不是L(m)的倍数即f(n)m。 b)g(n) m。条件 (b) 可能本身又是一个需要容斥原理来解决的计数问题。例如g(n)可能表示n的不同质因子个数或者n的某种约数和。统计满足g(n) m且n是L(m-1)倍数的数量可能需要枚举所有导致g(n) m的因子组合然后用容斥原理从总数中减去。在这种情况下容斥原理可能会嵌套使用外层用于划分f(n)的取值类别内层用于处理g(n)的条件计数。这要求解题者对集合的划分与容斥有非常清晰的认识。6. 实战技巧与避坑指南基于这类题目的普遍特点我总结了一些实战技巧和容易出错的地方6.1 LCM计算的溢出与精度这是最大的坑点。L(k)的增长速度远超指数。技巧1提前终止与溢出检查像我们代码中那样在乘法前用除法判断if a N / b是防止整数溢出的标准做法。不要先乘再比较。技巧2使用大整数库在Python中int是任意精度的所以不用担心。但在C/Java中对于极大的N如1e18即使使用unsigned long long计算L(k)的中间过程也可能溢出。一种策略是当L(k-1) N / k时即下一个LCM肯定超过N就停止枚举。另一种策略是使用__int128如果编译器支持或高精度库。技巧3利用质因数分解求LCM有时不需要显式计算LCM的具体值只需要知道N // L(k)是否为0。我们可以维护L(k)的质因数分解形式。L(k)是1..k中所有质数最高次幂的乘积。例如L(10) 2^3 * 3^2 * 5^1 * 7^1。判断L(k)是否整除n可以转化为检查n是否包含这些质因子及其足够的幂次。但在计数问题中直接使用floor(N / L)更直观。6.2 边界条件处理m的起始值在我们的例子中f(n)最小为2所以m从2开始。务必根据题目定义的函数最小值确定起始点。最后一个有效k处理序列的末尾很重要。当L(m)超过N时count(m) floor(N / L(m-1))。在代码中我们通过给L(m)赋一个大于N的值如N1来统一处理。空集与零值容斥原理计算中项数可能很多但很多项的贡献为0因为LCM超过N。有效的优化是只在LCM值不超过N时才进行DFS枚举子集。这可以大幅减少计算量。6.3 枚举子集的容斥实现如果问题需要枚举一个集合的所有子集进行容斥例如统计不能被集合S中任何数整除的数标准的写法是def count_numbers(N, S): # S 是一个正整数列表 m len(S) total 0 # 枚举子集掩码从1到(1m)-1 for mask in range(1, 1 m): lcm_val 1 bits 0 for i in range(m): if mask i 1: bits 1 # 计算lcm注意溢出 g math.gcd(lcm_val, S[i]) # 检查是否溢出或超过N if lcm_val N // (S[i] // g): lcm_val N 1 # 标记为超过N break lcm_val lcm_val * (S[i] // g) if lcm_val N: continue # 该项贡献为0 cnt N // lcm_val if bits % 2 1: # 奇加偶减 total cnt else: total - cnt # 最终不能被任何数整除的数的个数 N - total return N - total注意这里total计算的是“至少能被S中一个数整除”的数的个数根据容斥原理。我们最终要的是“不能被任何数整除”的个数所以用N减去它。6.4 调试与验证对于这类数学性强的题目一定要用暴力程序对小数据N较小进行验证确保公式推导和代码实现正确。写一个暴力计算f(n)的函数用于N 100的情况。对比暴力结果和优化算法结果必须完全一致。检查中间值打印出预处理得到的L(k)序列以及计算过程中的count(m)看是否符合预期。例如对于我们的问题暴力验证代码如下def f_bruteforce(n): k 1 while True: if n % k ! 0: return k k 1 def S_bruteforce(N): return sum(f_bruteforce(i) for i in range(1, N1)) N_test 100 print(f暴力结果 S({N_test}) {S_bruteforce(N_test)}) print(f算法结果 S({N_test}) {calculate_S(N_test)}) assert S_bruteforce(N_test) calculate_S(N_test) print(测试通过)7. 总结与思维提升“Strange Function”这类题目是算法竞赛中检验选手数论与组合数学能力的试金石。它不要求高深的模板但要求扎实的基础和灵活的思维。核心思维链条理解函数本质首先通过小规模枚举观察f(n)的值与n的因数、倍数之间的关系。尝试用数学语言描述这种关系。寻找数学对应往往能发现函数值与n被某个LCM序列整除的情况紧密相关。将“函数值等于m”转化为“n满足某个关于LCM的整除性质”。转化为计数问题求和或计数问题转化为对满足一系列条件的整数n进行计数。应用容斥原理当条件涉及“不能被a,b,c...整除”或“至少满足一个条件”时容斥原理是化“或”为“和”的标准工具。利用LCM进行计算容斥原理中的交集大小通过LCM计算。1..N中能被LCM(a,b,...)整除的数的个数就是floor(N / LCM(...))。优化枚举范围由于LCM快速增长有效的枚举项k值或子集非常有限使得算法从理论上的指数级变为实际上的常数级。掌握这道题你收获的不仅仅是一道题的解法而是一种解决复杂计数问题的通用框架定义 - 观察 - 建模 - 转化 - 应用已知定理/原理 - 计算优化。这种能力在解决其他涉及数论、组合、集合计数的题目时同样至关重要。下次再看到“奇怪”的函数不妨先试试暴力枚举找规律再想想能否和最小公倍数、容斥原理这些老朋友联系起来。
1. 项目概述从一道算法题看数论与组合思维的融合“2021-09-17C. Strange Function(lcm容斥)”这个标题乍一看像是某场编程竞赛很可能是Codeforces的一道题目记录。对于算法竞赛的选手或者对编程和数学感兴趣的朋友来说这背后隐藏的是一道典型的、将数论知识与组合思维深度结合的难题。它考察的远不止是写代码的能力更是对最小公倍数LCM和容斥原理这两个核心数学工具的深刻理解与灵活运用。这道题之所以值得深挖是因为它完美地展示了如何将一个看似复杂的“奇怪函数”计算问题通过数学建模转化为清晰可解的计数问题。如果你正在准备算法竞赛或者想挑战自己的逻辑与数学抽象能力理解这道题的解法会是一次极佳的训练。它不仅教你如何解题更教你一种“化繁为简”的通用思考方式。2. 核心思路拆解为什么是LCM与容斥要理解这道题我们首先得拆解“Strange Function”这个描述。虽然题目原文没有给出但结合“lcm容斥”这个关键提示我们可以推断出题目的典型结构通常这类题目会定义一个函数f(n)它可能与n的某些特定性质的约数、倍数或者不能被某个集合中任何数整除的数有关。而求解的目标往往是计算f(1) f(2) ... f(N)的和或者某个区间内满足f(n) g(n)的n的个数等。2.1 LCM的核心角色定义“步长”与“周期”为什么LCM会出现在这里想象一下如果题目条件与“不能被a或b整除”相关那么“能被a整除”和“能被b整除”的数其出现是有周期的。这个周期正是a和b的最小公倍数 LCM(a, b)。例如考虑所有不能被2或3整除的正整数。数字2的倍数是每2个出现一次3的倍数是每3个出现一次。而同时是2和3的倍数即能被6整除的数它们被重复计算了。这里6就是LCM(2,3)。当我们从总数中减去2的倍数和3的倍数时6的倍数被减了两次所以需要加回来一次。这已经触及了容斥原理的雏形。更复杂的情况是题目条件可能涉及多个数或者与LCM本身直接相关。例如函数f(n)可能被定义为最小的正整数x使得n不能被x整除而这个x又可能与1, 2, 3, ...的LCM序列有关。这时LCM序列L(k) LCM(1, 2, ..., k)的性质就成为解题关键。L(k)增长非常快这允许我们枚举有限的k来处理极大的n。关键思路在算法题中LCM常常用于刻画一组数共同的“影响周期”或“性质边界”。通过枚举这个周期或边界的指数k我们可以将无穷的或大规模的枚举问题转化为对有限个区间的统计问题。2.2 容斥原理的作用处理“或”与“且”的逻辑关系容斥原理是处理集合交并问题的利器。其基本公式对于两个集合A和B是|A ∪ B| |A| |B| - |A ∩ B|。推广到多个集合就是加上所有单个集合大小减去所有两两交集大小加上所有三三交集大小以此类推正负号交替。在这类题目中集合通常被定义为“满足某个条件的数”。例如集合A能被a整除的数。集合B能被b整除的数。 那么“能被a或b整除的数”就是A ∪ B而“既不能被a也不能被b整除的数”就是总数减去|A ∪ B|。当条件变得更复杂比如“不能被1, 2, ..., k中任何一个数整除”我们要求的集合就是所有这些“能被i整除”的集合的并集的补集。直接计算补集大小很困难但计算并集大小可以通过容斥原理来实现。容斥原理将复杂的“或”条件分解为若干个“且”条件的加减组合而“且”条件同时能被若干个数整除对应的集合其大小恰恰可以通过这些数的LCM来方便计算即能被LCM整除的数的个数。2.3 思路融合LCM为容斥提供计算单元至此两者的关系就清晰了问题转化将原问题定义的f(n)或计数条件转化为对一系列集合通常与“整除性”相关的并集或交集的操作。容斥框架使用容斥原理将并集的计算分解为多个子集交集的代数和。LCM计算每一个子集交集例如“同时能被a和b整除的数”其元素个数等于floor(N / LCM(a, b))。这里LCM提供了计算交集大小的直接公式。枚举优化由于LCM增长极快参与容斥的集合通常是1到某个k的整数的子集数量看似是指数级的2^k但实际上当子集的LCM超过上界N时其对结果的贡献为0。因此有效的子集数量是有限的可以通过DFS或位运算枚举来高效实现。3. 典型问题还原与抽象建模虽然我们没有原题但我们可以构建一个与标题描述高度吻合的经典问题模型并给出完整的解决方案。这是算法竞赛中一种常见的题型。假设题目如下定义函数f(n)为最小的正整数k使得n不能被k整除。例如f(1) 2因为1能被1整除但不能被2整除f(2) 32能被1和2整除但不能被3整除f(6) 46能被1,2,3整除但不能被4整除。 给定一个整数N求f(1) f(2) ... f(N)的和。3.1 问题分析与观察首先我们暴力计算小范围的f(n)来寻找规律n1: 除数1(可), 2(不可) - f2n2: 除数1,2(可), 3(不可) - f3n3: 除数1,2,3(可), 4(不可) - f4n4: 除数1,2,3,4(可), 5(不可) - f5n5: 除数1,2,3,4,5(可), 6(不可) - f6n6: 除数1,2,3(可), 4(不可) - f4我们发现对于大多数数f(n)似乎等于n1但n6就是一个反例。f(6)4因为6能被1,2,3整除但不能被4整除。那么n在什么情况下f(n) ! n1呢当存在一个小于n1的数k使得n能被所有小于k的正整数整除但不能被k整除时f(n)就会小于n1。这引出了一个关键概念如果一个数n能被1, 2, ..., k中的所有数整除那么n一定是它们的最小公倍数L(k) LCM(1,2,...,k)的倍数。换句话说n是L(k)的倍数是n能被1..k整除的充要条件。因此我们可以重新描述f(n)找到最大的k使得n是L(k)的倍数。那么f(n) k1。因为n能被1..k整除但不能被k1整除否则k就不是最大的。3.2 数学模型建立设L(k) LCM(1, 2, ..., k)。序列如下L(1)1, L(2)2, L(3)6, L(4)12, L(5)60, L(6)60, L(7)420, L(8)840, L(9)2520, L(10)2520, L(11)27720, L(12)27720, L(13)360360, L(14)360360, L(15)360360, L(16)720720, L(17)12252240, ... 可以看到L(k)增长非常迅速。对于给定的nf(n) k1其中k是满足L(k)整除n的最大整数。 那么求和S(N) Σ_{n1}^{N} f(n)可以转化为按k来分类计数。如何转化考虑所有满足f(n) m的n。根据定义这意味着n能被L(m-1)整除因为k m-1是最大的。n不能被L(m)整除否则k至少是m。因此f(n) m当且仅当n属于集合{ n | L(m-1) | n 且 L(m) ∤ n }。 这个集合可以表示为A {n: L(m-1)的倍数} \ {n: L(m)的倍数}。 而L(m)一定是L(m-1)的倍数因为L(m) LCM(L(m-1), m)所以{n: L(m)的倍数}是{n: L(m-1)的倍数}的子集。于是满足f(n)m的n的个数为count(m) floor(N / L(m-1)) - floor(N / L(m))。3.3 引入容斥原理上面的推导已经很清晰了似乎不需要容斥其实这正是容斥原理最简单形式两个集合的差的应用。我们把它写得更形式化一点设集合U为[1, N]的所有整数。 设集合A {ninU|L(m-1)整除n}。 设集合B {ninU|L(m)整除n}。 我们知道B ⊆ A。 那么我们想要的集合CA \ BA ∩ (U \ B)。 根据容斥原理|C| |A| - |A ∩ B|。由于B ⊆ A所以A ∩ B B。 因此|C| |A| - |B| floor(N/L(m-1)) - floor(N/L(m))。这与我们之前的推导一致。对于更复杂的原始问题可能不是求f(n)的和而是求满足f(n) g(n)的n的个数容斥原理可能会以更复杂的形式出现例如需要处理多个不等式条件的交集。3.4 求和计算现在总和S(N) Σ_{n1}^{N} f(n) Σ_{m} m * count(m)其中m从2开始因为f(n)最小为2。 但是m可以到无穷大吗不。因为当L(m-1) N时floor(N / L(m-1)) 0count(m)为0。所以m只需要枚举到满足L(m-1) N的最大值即可。由于L(k)增长极快m的范围非常小对于N高达1e16m通常也不超过几十。因此算法步骤如下预处理计算出L(k)序列直到L(k) N。对于m从2开始计算count(m) N // L(m-1) - N // L(m)。注意这里//表示整数除法向下取整。L(1)定义为1以保证m2时L(m-1)L(1)1N//1 N。累加m * count(m)到答案中。还需要考虑边界对于那些f(n) m_max1的数即能被L(m_max)整除的数我们的公式中count(m_max1) N//L(m_max) - N//L(m_max1)而L(m_max1) N所以N//L(m_max1)0。因此count(m_max1) N//L(m_max)。这正好对应了所有能被最大L(k)整除的n它们的f(n)确实都是m_max1。计算示例N6预处理 L: L(1)1, L(2)2, L(3)6, L(4)126所以 m_max 3因为 L(3)66。m2: count 6//L(1) - 6//L(2) 6//1 - 6//2 6 - 3 3。贡献2 * 3 6。 对应 n1,3,5f值均为2m3: count 6//L(2) - 6//L(3) 6//2 - 6//6 3 - 1 2。贡献3 * 2 6。 对应 n2,4f值均为3m4: count 6//L(3) - 6//L(4) 6//6 - 6//12 1 - 0 1。贡献4 * 1 4。 对应 n6f值为4总和 S 6 6 4 16。 手动验证f(1)f(2)f(3)f(4)f(5)f(6)23456424等等这里出错了。我们手动算一下f(1)2, f(2)3, f(3)4, f(4)5, f(5)6, f(6)4。和是23456424。我们的算法算出16显然不对。问题出在哪里我们的推导f(n) k1中k是满足L(k)整除n的最大整数。对于 n3L(1)1整除3L(2)2不整除3所以 k1f(3)2但实际 f(3)4。矛盾仔细检查定义f(n)是最小的正整数k使得n不能被k整除。 对于 n3:k1: 3能被1整除。k2: 3不能被2整除是的3除以2余1。所以最小的 k 就是2。 但根据我们之前的计算f(3)应该是2而不是4。我最初举例时写错了纠正f(3)2, f(4)3, f(5)2, f(6)4。 重新计算f(1)2, f(2)3, f(3)2, f(4)3, f(5)2, f(6)4。和为23232416。这与我们算法计算的结果一致所以我们的模型和算法是正确的。这个错误恰恰说明了理解定义的重要性。f(n)是最小的k使得n不能被k整除而不是“最大的k使得n能被1..k整除再加一”。后者是另一种常见函数定义有时称为g(n)。我们的算法实际上解决的是我们重新正确定义的这个问题。4. 算法实现与细节剖析基于上述数学模型我们可以给出高效的算法实现。这里以计算S(N)为例N可以非常大比如1e16。4.1 预处理LCM序列这是算法的关键步骤。我们需要计算L(k) LCM(1, 2, ..., k)。直接循环计算LCM会很快溢出即使使用大整数L(k)的增长也使得我们只需要计算很少的几项。计算L(k)时可以利用性质L(k) L(k-1) * (k / gcd(L(k-1), k))。但更需要注意的是溢出问题。由于我们只关心L(k) N的项当计算过程中L(k)即将超过N时我们可以提前终止。并且由于我们只需要L(k)的值来进行除法N // L(k)当L(k) N时这个除法结果为0我们可以用一个特殊值如N1或0来表示“无穷大”并在计算中判断。实现要点使用64位无符号整数如C的unsigned long long或语言自带的大整数类型如Python的int。在计算L(k)时每次乘法后立即检查是否超过N。如果超过可以标记该L(k)为N并停止后续计算因为后续的L(k)只会更大。存储两个数组lcm[k]存储L(k)的值或标记为N以及一个布尔数组表示是否有效。def preprocess_lcm_until(N): lcm_list [1] # index 0 占位lcm_list[i] 表示 L(i) k 1 current_lcm 1 while True: # 计算 L(k) LCM(current_lcm, k) # 使用 math.gcd 计算最大公约数 import math g math.gcd(current_lcm, k) # 先做除法防止中间溢出 temp current_lcm // g # 检查乘法是否会导致结果超过 N if temp N // k: # 等价于 if temp * k N: # 超过 N后续的 L(k) 都会超过 N停止预处理 break current_lcm temp * k lcm_list.append(current_lcm) k 1 return lcm_list # 示例N10^9 N 10**9 lcm_seq preprocess_lcm_until(N) print(f预处理得到的 L(k) 序列 (直到 {N}): {lcm_seq}) print(f最大的 k 使得 L(k) {N} 是: {len(lcm_seq)-1})4.2 核心求和计算得到lcm_seq后求和计算就非常直接了。注意索引对应关系lcm_seq[i]对应L(i)。def calculate_S(N): lcm_seq preprocess_lcm_until(N) # lcm_seq[0] L(0) 我们定义为1但通常从 L(1) 开始用。这里调整一下。 # 更清晰的写法让 lcm_seq[k] 直接表示 L(k) # 我们预处理时 lcm_list[0]1 (L(1)?)不我们让索引对齐lcm_seq[1] L(1)1 # 但为了计算方便我们通常使用 lcm_seq 作为列表lcm_seq[m] 表示 L(m) # 根据预处理函数lcm_list[0]L(1)1, lcm_list[1]L(2)2, ... # 我们令 lcm_seq[m] L(m)则需要将预处理结果前插一个 L(0)1根据定义L(0)可视为1。 # 实际上在公式 count(m) N//L(m-1) - N//L(m) 中m 从2开始需要 L(1)。 # 简单起见我们构建一个数组 L其中 L[i] 表示 L(i) L [1] # L[0] 1 (方便索引但不用) L.extend(lcm_seq) # 现在 L[1] 1, L[2] 2, L[3] 6, ... # 但我们的预处理结果 lcm_seq 第一个元素已经是 L(1)1所以直接使用它作为 L[1:] # 调整preprocess_lcm_until 返回的列表第一个是 L(1)我们把它当作 L[1] L [0] lcm_seq # L[1] lcm_seq[0], L[2] lcm_seq[1], ... ans 0 M len(L) - 1 # 最大的有效索引L[M] N, L[M1] N 或不存在 for m in range(2, M2): # m 从2到 M1 L_m_1 L[m-1] # L(m-1) # 计算 L(m)如果 m M则 L[m] 有效否则视为无穷大N L_m L[m] if m M else (N 1) # 用 N1 表示 N这样 N // (N1) 0 count_m N // L_m_1 - N // L_m ans m * count_m return ans4.3 复杂度分析时间复杂度预处理 LCM 序列的复杂度为 O(K)其中 K 是满足L(K) N的最大整数。由于L(k)增长超指数级K 非常小。对于N高达10^16K 大约在 40-50 左右。求和循环也是 O(K)。因此总时间复杂度是 O(K)对于任何合理的 N 都是常数时间。空间复杂度O(K)用于存储 LCM 序列。这效率极高完全能够处理极限大的N。5. 容斥原理的更一般化应用场景在我们这个问题中容斥原理的应用相对简单两个集合的差。但在许多其他“Strange Function”类题目中容斥可能需要处理更多集合。典型场景扩展假设问题变为计算1到N中有多少个数n满足f(n) g(n)其中g(n)是另一个函数。 解题步骤往往如下将条件f(n) g(n)分解。通常f(n)和g(n)都可以表示为基于n的整除性质的函数。固定f(n)的可能取值。例如f(n)可能取值2, 3, 4, ...对应n是L(1), L(2), ...的倍数但不是L(2), L(3), ...的倍数。对于每个固定的f(n) m条件f(n) g(n)转化为g(n) m。而g(n)往往也可以根据n的因子情况确定一个值。此时我们需要统计满足以下两个条件的n的个数 a)n是L(m-1)的倍数但不是L(m)的倍数即f(n)m。 b)g(n) m。条件 (b) 可能本身又是一个需要容斥原理来解决的计数问题。例如g(n)可能表示n的不同质因子个数或者n的某种约数和。统计满足g(n) m且n是L(m-1)倍数的数量可能需要枚举所有导致g(n) m的因子组合然后用容斥原理从总数中减去。在这种情况下容斥原理可能会嵌套使用外层用于划分f(n)的取值类别内层用于处理g(n)的条件计数。这要求解题者对集合的划分与容斥有非常清晰的认识。6. 实战技巧与避坑指南基于这类题目的普遍特点我总结了一些实战技巧和容易出错的地方6.1 LCM计算的溢出与精度这是最大的坑点。L(k)的增长速度远超指数。技巧1提前终止与溢出检查像我们代码中那样在乘法前用除法判断if a N / b是防止整数溢出的标准做法。不要先乘再比较。技巧2使用大整数库在Python中int是任意精度的所以不用担心。但在C/Java中对于极大的N如1e18即使使用unsigned long long计算L(k)的中间过程也可能溢出。一种策略是当L(k-1) N / k时即下一个LCM肯定超过N就停止枚举。另一种策略是使用__int128如果编译器支持或高精度库。技巧3利用质因数分解求LCM有时不需要显式计算LCM的具体值只需要知道N // L(k)是否为0。我们可以维护L(k)的质因数分解形式。L(k)是1..k中所有质数最高次幂的乘积。例如L(10) 2^3 * 3^2 * 5^1 * 7^1。判断L(k)是否整除n可以转化为检查n是否包含这些质因子及其足够的幂次。但在计数问题中直接使用floor(N / L)更直观。6.2 边界条件处理m的起始值在我们的例子中f(n)最小为2所以m从2开始。务必根据题目定义的函数最小值确定起始点。最后一个有效k处理序列的末尾很重要。当L(m)超过N时count(m) floor(N / L(m-1))。在代码中我们通过给L(m)赋一个大于N的值如N1来统一处理。空集与零值容斥原理计算中项数可能很多但很多项的贡献为0因为LCM超过N。有效的优化是只在LCM值不超过N时才进行DFS枚举子集。这可以大幅减少计算量。6.3 枚举子集的容斥实现如果问题需要枚举一个集合的所有子集进行容斥例如统计不能被集合S中任何数整除的数标准的写法是def count_numbers(N, S): # S 是一个正整数列表 m len(S) total 0 # 枚举子集掩码从1到(1m)-1 for mask in range(1, 1 m): lcm_val 1 bits 0 for i in range(m): if mask i 1: bits 1 # 计算lcm注意溢出 g math.gcd(lcm_val, S[i]) # 检查是否溢出或超过N if lcm_val N // (S[i] // g): lcm_val N 1 # 标记为超过N break lcm_val lcm_val * (S[i] // g) if lcm_val N: continue # 该项贡献为0 cnt N // lcm_val if bits % 2 1: # 奇加偶减 total cnt else: total - cnt # 最终不能被任何数整除的数的个数 N - total return N - total注意这里total计算的是“至少能被S中一个数整除”的数的个数根据容斥原理。我们最终要的是“不能被任何数整除”的个数所以用N减去它。6.4 调试与验证对于这类数学性强的题目一定要用暴力程序对小数据N较小进行验证确保公式推导和代码实现正确。写一个暴力计算f(n)的函数用于N 100的情况。对比暴力结果和优化算法结果必须完全一致。检查中间值打印出预处理得到的L(k)序列以及计算过程中的count(m)看是否符合预期。例如对于我们的问题暴力验证代码如下def f_bruteforce(n): k 1 while True: if n % k ! 0: return k k 1 def S_bruteforce(N): return sum(f_bruteforce(i) for i in range(1, N1)) N_test 100 print(f暴力结果 S({N_test}) {S_bruteforce(N_test)}) print(f算法结果 S({N_test}) {calculate_S(N_test)}) assert S_bruteforce(N_test) calculate_S(N_test) print(测试通过)7. 总结与思维提升“Strange Function”这类题目是算法竞赛中检验选手数论与组合数学能力的试金石。它不要求高深的模板但要求扎实的基础和灵活的思维。核心思维链条理解函数本质首先通过小规模枚举观察f(n)的值与n的因数、倍数之间的关系。尝试用数学语言描述这种关系。寻找数学对应往往能发现函数值与n被某个LCM序列整除的情况紧密相关。将“函数值等于m”转化为“n满足某个关于LCM的整除性质”。转化为计数问题求和或计数问题转化为对满足一系列条件的整数n进行计数。应用容斥原理当条件涉及“不能被a,b,c...整除”或“至少满足一个条件”时容斥原理是化“或”为“和”的标准工具。利用LCM进行计算容斥原理中的交集大小通过LCM计算。1..N中能被LCM(a,b,...)整除的数的个数就是floor(N / LCM(...))。优化枚举范围由于LCM快速增长有效的枚举项k值或子集非常有限使得算法从理论上的指数级变为实际上的常数级。掌握这道题你收获的不仅仅是一道题的解法而是一种解决复杂计数问题的通用框架定义 - 观察 - 建模 - 转化 - 应用已知定理/原理 - 计算优化。这种能力在解决其他涉及数论、组合、集合计数的题目时同样至关重要。下次再看到“奇怪”的函数不妨先试试暴力枚举找规律再想想能否和最小公倍数、容斥原理这些老朋友联系起来。
