1. 项目概述从一道竞赛题看数论思维的实战应用“Strange Function”这个标题乍一看有点让人摸不着头脑但加上“lcm”和“容斥”这两个关键词熟悉算法竞赛的朋友们大概就能会心一笑了。这通常指的是一道来自Codeforces等在线评测平台本题编号为CF 2021-09-17的C题的经典数论问题。这类题目不会让你去实现一个具体的“奇怪函数”而是要求你分析这个函数在特定数学定义下的行为并高效计算出它在某个范围内的取值之和或满足某些条件的个数。核心的挑战在于直接模拟计算在数据范围n可能高达10^16下是完全不可行的必须依靠深刻的数学洞察力将问题转化为关于最小公倍数LCM和容斥原理Inclusion-Exclusion Principle的模型。今天我们就来彻底拆解这道题背后的思维链条不仅搞懂怎么做更要弄明白为什么这么做以及如何将这种“数论组合”的思维模式应用到更广泛的场景中。2. 问题核心定义与暴力解法的不可行性2.1 “奇怪函数” f(i) 的数学定义题目通常会这样定义函数 f(i)对于正整数 if(i) 等于最小的正整数 x使得 x 不是 i 的约数。换句话说我们从1开始逐个检查正整数第一个不能整除 i 的数就是 f(i) 的值。我们来举几个例子直观感受一下i 1: 检查11能整除1检查22不能整除1所以 f(1) 2。i 2: 检查1能整除检查2能整除检查3不能整除所以 f(2) 3。i 3: 检查1能整除检查2不能整除所以 f(3) 2。i 4: 检查1能整除检查2能整除检查3不能整除所以 f(4) 3。i 6: 检查1能整除检查2能整除检查3能整除检查4不能整除所以 f(6) 4。题目最终要求的是计算 S(n) f(1) f(2) ... f(n) 对某个大质数如1e97取模的结果其中 n 可以非常大。2.2 为什么不能暴力计算最朴素的想法是写一个循环对每个 i 从1到n再内层循环从1开始找第一个不能整除 i 的 x累加 f(i)。我们来简单估算一下复杂度。对于每个 i寻找 f(i) 平均可能需要 O(sqrt(i)) 次检查因为一个数的约数大约在这个数量级。那么总复杂度就是 O(n * sqrt(n))。当 n10^5 时这已经是 10^7.5 次操作勉强在极限边缘。但当 n 达到题目可能的上限 10^16 时这个计算量是宇宙寿命都无法完成的。因此我们必须寻找函数 f(i) 的数学规律找到一种能够批量、快速计算大量 f(i) 值之和的方法。2.3 关键观察f(i) 的值由 i 的“约数覆盖情况”决定重新审视 f(i) 的定义它是第一个不能整除 i 的正整数。那么反过来想所有比 f(i) 小的正整数即1, 2, ..., f(i)-1都必须能整除 i。这意味着i 必须是这些数的最小公倍数LCM的倍数。设 L(k) lcm(1, 2, ..., k)即前 k 个正整数的最小公倍数。那么如果 f(i) x则意味着i 是 L(x-1) 的倍数因为1到x-1都能整除i。i 不是 L(x) 的倍数如果i是L(x)的倍数那么x也能整除i这与f(i)x矛盾。这个观察是解决问题的基石。它将一个关于“整除性”的函数求值问题转化为了一个关于“最小公倍数倍数”的计数问题。3. 核心思路转化从求值到计数3.1 建立数学模型根据上面的观察对于给定的 xx 2哪些 i 会满足 f(i) x 呢条件Ai 是 L(x-1) 的倍数。条件Bi 不是 L(x) 的倍数。在1到n的范围内满足条件A的 i 的个数是 floor(n / L(x-1))即 n 除以 L(x-1) 的整数部分。 但这些 i 中有一部分也同时是 L(x) 的倍数它们不满足条件B。而 L(x) 必然是 L(x-1) 的倍数因为前x个数的LCM肯定包含前x-1个数的LCM所以满足条件A的 i 中是 L(x) 倍数的那些实际上就是满足“i 是 L(x) 的倍数”的 i。其个数为 floor(n / L(x))。因此在1到n中严格满足“是 L(x-1) 的倍数但不是 L(x) 的倍数”的 i 的个数为count(x) floor(n / L(x-1)) - floor(n / L(x))这些 i 的 f(i) 值都等于 x。那么所有这些 i 对总和 S(n) 的贡献就是x * count(x)。3.2 求和公式的推导于是我们得到了计算 S(n) 的关键公式S(n) Σ_{x2}^{∞} [ x * ( floor(n / L(x-1)) - floor(n / L(x)) ) ]这里 x 的上限为什么是无穷因为当 x 增大到一定程度L(x-1) 会超过 n那么 floor(n / L(x-1)) 就等于0后续的项也就都是0了求和实际上会在有限项内终止。这个公式的美妙之处在于它将一个对 i 的求和O(n)复杂度转化为了一个对 x 的求和。而 x 的增长对应的 L(x) 增长极快使得需要计算的项数非常少。3.3 L(k) 的增长速度与计算项数估计L(k) 是前 k 个正整数的最小公倍数。它被称为“最小公倍数函数”增长速率比指数函数还要快。具体来说L(1) 1L(2) lcm(1,2) 2L(3) lcm(2,3) 6L(4) lcm(6,4) 12L(5) lcm(12,5) 60L(6) lcm(60,6) 60L(7) lcm(60,7) 420...可以观察到L(k) 在 k 是质数或质数幂时会显著增长。实际上L(k) 约等于 e^{k(1o(1))} 量级。对于 n 高达 10^16当 L(x-1) n 时floor(n / L(x-1))为0。计算可知L(50) 的数量级已经远超 10^16。因此在实际计算中x 只需要从2枚举到大约50-60求和就会自然终止。复杂度从 O(n) 降到了 O(K)其中 K ~ 50-60这是质的飞跃。4. 算法实现与细节剖析4.1 算法流程预处理 L 数组计算 L(1), L(2), ..., L(K)。其中 K 是一个足够大的数确保 L(K) n例如取K60。计算 L(k) 可以用递推L(k) lcm(L(k-1), k)。初始化答案ans 0。枚举 x 进行求和for x from 2 to K:。计算term (n // L(x-1) - n // L(x)) % MOD。这里//表示整数除法floor。将贡献加入答案ans (ans x * term) % MOD。输出答案ans即为 S(n) % MOD 的结果。4.2 关键代码实现与注意事项MOD 10**9 7 def solve(): n int(input()) # 假设输入n # 1. 预处理LCM数组 L [1] * (60) # L[0]对应L(1)? 为了清晰我们让下标从1开始 # 更清晰的写法用一个列表l[k] 表示 L(k) l [1] * (65) # 多开一点空间 for k in range(2, 65): # 计算 lcm(l[k-1], k) # 由于l[k-1]和k可能很大直接使用 gcd 公式计算 from math import gcd g gcd(l[k-1], k) l[k] l[k-1] // g * k if l[k] n: # 一旦超过n就可以停止预处理因为后续项贡献为0 max_k k break else: max_k 64 # 如果循环正常结束说明n极大但我们的范围也够了 # 2. 枚举x求和 ans 0 for x in range(2, max_k 1): # x从2到max_k count (n // l[x-1]) - (n // l[x]) ans (ans count * x) % MOD print(ans % MOD)注意事项LCM的溢出问题在计算l[k] l[k-1] // g * k时即使l[k-1]和k没有溢出编程语言整数范围但中间的乘法l[k-1] * k可能会溢出。在Python中整数是任意精度的所以没问题。但在C/Java中需要使用long long并注意在乘法前判断是否超过n因为我们只关心l[k]是否小于等于n或者使用int128或高精度。循环终止条件预处理 LCM 时一旦l[k] n就可以停止因为对于更大的 kL(k-1) l[k] nfloor(n / L(k-1))肯定为0。这可以节省不必要的计算。MOD运算的位置公式中的count可能很大但在与x相乘前先取模是安全的因为(a-b) % MOD * c % MOD等价于( (a-b)*c ) % MOD。我们可以在计算ans时每一步都取模。4.3 思维延伸为什么是容斥原理有同学可能会问标题中的“容斥”体现在哪里在我们推导count(x) floor(n / L(x-1)) - floor(n / L(x))时其实已经用到了最简单的容斥思想两个集合的容斥。集合 A{ i | 1in, i % L(x-1) 0 }大小|A| floor(n / L(x-1))。集合 B{ i | 1in, i % L(x) 0 }大小|B| floor(n / L(x))。 我们需要的是属于 A 但不属于 B 的元素个数即|A| - |A∩B|。由于 B 是 A 的子集L(x)是L(x-1)的倍数所以是L(x)倍数的数一定是L(x-1)的倍数因此A∩B B。所以|A| - |A∩B| |A| - |B|。这就是我们公式的来源。对于更复杂的问题可能需要处理更多集合的交并容斥原理的公式会更加复杂。5. 实战演练与复杂度分析5.1 以 n10 为例进行演算让我们手动计算 S(10) 来验证思路。 首先列出 L(k):L(1)1, L(2)2, L(3)6, L(4)12, L(5)60, L(6)60...现在枚举 x:x2: count floor(10/L(1)) - floor(10/L(2)) 10/1 - 10/2 10 - 5 5。贡献 2*510。 验证i1,3,5,7,9 的 f(i) 都是2共5个x3: count floor(10/L(2)) - floor(10/L(3)) 5 - floor(10/6)5-14。贡献 3*412。 验证i2,4,8,10 的 f(i) 都是3共4个x4: count floor(10/L(3)) - floor(10/L(4)) 1 - floor(10/12)1-01。贡献 4*14。 验证i6 的 f(i)4共1个x5: L(4)12 10 floor(10/L(4))0。但我们需要 floor(10/L(4)) 和 floor(10/L(5))。L(5)60。 count floor(10/L(4)) - floor(10/L(5)) 0 - 0 0。贡献0。 后续 x5 时因为 L(x-1) 10第一项就是0贡献均为0。总和 S(10) 10 12 4 26。 我们可以暴力列出 f(1)到f(10): 2,3,2,3,2,4,2,3,2,3。求和 2323242323 26。完全正确。5.2 算法复杂度分析时间复杂度预处理 LCM 数组需要 O(K) 次运算其中 K 是满足 L(K) n 的最小整数大约在 log(n) 级别但更准确地说是 O(几十)。求和循环也是 O(K)。因此总时间复杂度为 O(K)对于 n10^16K~50-60是常数时间。空间复杂度只需要存储长度为 O(K) 的 LCM 数组是常数空间。5.3 边界条件与陷阱x 的起始值f(i) 的最小值是2当 i 是奇数时所以我们的求和从 x2 开始。公式中使用了 L(x-1)因此需要定义好 L(1)1。大数取模题目通常要求对一个大质数如1e97取模。在计算count * x时count可能很大最大可达 nx最大为 K。直接相乘可能超出64位整数范围在C中需要在乘法前后及时取模或者使用__int128。LCM 的计算效率计算 lcm(a, b) 时使用公式a / gcd(a,b) * b。注意计算顺序先做除法再做乘法避免中间结果溢出。在预处理时如果发现l[k-1] / gcd * k n我们可以直接设置l[k] n1或一个大于 n 的值来提前终止有效计算因为具体值超过 n 后对我们就没有意义了floor(n / L)为0。6. 问题变形与思维拓展6.1 如果函数定义变化假设函数 g(i) 定义为“最小的质数 p使得 p 不能整除 i”。我们还能用类似方法吗 分析如果 g(i)p那么所有小于 p 的质数都能整除 i且 p 不能整除 i。设 P(k) 为前 k 个质数的乘积。那么条件转化为i 是 P(k-1) 的倍数但不是 P(k) 的倍数其中 p_k 是第 k 个质数。问题就化归为和原题几乎相同的形式只是把 L(k) 换成了前 k 个质数的乘积 P(k)。由于质数乘积增长也非常快阶乘级别需要枚举的项数同样很少。6.2 求满足 f(i) C 的 i 的个数如果问题不是求和而是求在 1 到 n 范围内有多少个 i 满足 f(i) xx给定。这就是我们推导过程中的count(x)本身floor(n / L(x-1)) - floor(n / L(x))。直接计算即可。6.3 处理多个查询如果题目有多个独立的 n 需要查询比如 t 组查询每组一个 n我们还能预处理什么 由于不同的 n 对应的有效 K使 L(K)n不同LCM 数组本身是固定的只与下标有关。我们可以预处理出一个足够长的 LCM 数组比如计算到 L(60)。对于每个查询 n我们仍然需要从 x2 开始求和直到L(x-1) n时停止。因为 K 很小对每个查询做一次 O(K) 的求和是完全可接受的。预处理 LCM 数组是 O(K) 一次总复杂度 O(t*K K)。6.4 从这道题中学到的思维模式这道题的精髓在于“改变枚举主体”和“利用数学性质批量计数”。暴力枚举的困境原始问题是枚举 i (1到n)对每个 i 求 f(i)。n 太大不可行。洞察与转化发现 f(i)x 等价于 i 满足特定的关于 LCM 的整除性质。逆转主元转而枚举可能的函数值 x。因为 f(i) 的取值范围虽然理论上是所有 2 的整数但使得 L(x-1) n 的 x 非常少。批量计数对于每个 x利用 floor 除法公式 O(1) 计算出有多少个 i 满足 f(i)x从而批量计算出这些 i 对总和的贡献。这种“枚举答案值组合计数”的思路在数论、组合数学的竞赛题中非常常见是优化指数级复杂度的利器。7. 常见错误与调试技巧7.1 错误类型汇总LCM计算溢出在C中使用lcm a / gcd * b时a / gcd的结果可能没问题但乘以b时可能溢出long long。解决方案提前判断如果a / gcd LLONG_MAX / b则说明会溢出此时可以直接将 LCM 设为一个大于 n 的哨兵值。循环终止条件错误在枚举 x 求和时不能简单地循环到固定值比如60而应该判断L(x-1) n作为继续循环的条件。否则当 n 很小时会做很多无用功虽然不影响结果但不优雅。取模错误count (n / L(x-1) - n / L(x))这个差值可能为负数吗不会因为L(x)是L(x-1)的倍数所以n / L(x-1)一定大于等于n / L(x)。但在编程中由于是整数除法确保使用无符号整数或确保结果非负即可。忽略 f(i) 的最小值有的同学可能从 x1 开始枚举。但 f(i) 最小为2所以 x 应从2开始。从1开始会导致多算一项x1且 L(0) 没有定义。7.2 调试与验证策略小数据暴力对拍写一个 O(n^2) 或 O(n sqrt(n)) 的暴力程序对于 n 1000 验证算法正确性。这是确保思维逻辑和代码实现无误的最有效方法。打印中间结果对于中等大小的 n如1e4可以打印出计算过程中的L(x),count(x),贡献值观察其变化趋势看是否符合预期L(x)快速增长count(x)快速减少。关注拐点检查当L(x-1)刚刚超过 n 时count(x)是否变为0后续贡献是否不再增加。7.3 一个高效的C实现参考#include bits/stdc.h using namespace std; using ll long long; const int MOD 1e9 7; const ll INF 1e16; // 大于题目n的最大值 ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } int main() { int T; cin T; // 预处理LCM序列直到其值超过可能的最大n这里设为1e16 vectorll L {1}; // L[0] L(1) 1 for (int k 2; ; k) { ll g gcd(L.back(), k); // 防止溢出计算如果 L.back()/g INF/k则说明下一项LCM肯定超过INF if (L.back() / g INF / k) { // 如果已经超过我们可以多推一项作为哨兵或者直接break L.push_back(INF 1); // 哨兵值保证大于任何n break; } ll nxt L.back() / g * k; L.push_back(nxt); if (nxt INF) break; // 超过范围停止预处理 } while (T--) { ll n; cin n; ll ans 0; // 枚举 x其中 L[x-2] 对应 L(x-1), L[x-1] 对应 L(x) // 我们的L数组下标: L[0]L(1), L[1]L(2), ... // 所以对于x需要 L(x-1) L[x-2], L(x) L[x-1] for (int x 2; ; x) { ll Lx_1 L[x-2]; // L(x-1) if (Lx_1 n) break; // 核心终止条件 ll Lx L[x-1]; // L(x) ll cnt n / Lx_1 - n / Lx; cnt % MOD; ans (ans cnt * x) % MOD; } cout ans \n; } return 0; }这个实现考虑了多组查询、溢出处理和提前终止是比较工业级的写法。8. 总结与高阶思考回顾整个解题过程我们从一个看似需要 O(n) 枚举的求和问题通过深入分析函数定义将其转化为一个基于 LCM 和容斥原理的计数问题最终得到了一个 O(log n) 级别实际上是常数的优雅解法。这道题完美地展示了数论和组合思维在算法竞赛中的威力。更深层的启示关注函数的“逆问题”与其思考给定 i 求 f(i)不如思考给定值 x哪些 i 能满足 f(i)x。这种“求逆”或“分类讨论”的思想是组合计数的核心。寻找不变量和快速增长量LCM 函数的爆炸性增长是我们能够大幅减少枚举范围的关键。在算法设计中寻找那些随参数增长极快的量往往是优化复杂度的突破口。容斥原理的灵活运用本题只用到了两个集合的简单容斥但其思想是普适的。对于更复杂的条件如“能被a或b整除”、“不能被a且不能被b整除”容斥原理是系统化计数的标准工具。最后虽然这道题背景是竞赛但其中蕴含的“转化问题”、“批量计数”、“利用数学性质简化计算”的思想在软件开发、数据分析甚至理论研究中都时有体现。下次当你遇到一个需要遍历大量数据求某个函数和的问题时不妨停下来想一想这个函数值背后是否隐藏着可以批量归类的数学结构