1. 项目概述：从一道竞赛题看数论思维的实战应用

“Strange Function”这个标题，乍一看有点让人摸不着头脑，但加上“lcm”和“容斥”这两个关键词，熟悉算法竞赛的朋友们大概就能会心一笑了。这通常指的是一道来自Codeforces等在线评测平台（本题编号为CF 2021-09-17的C题）的经典数论问题。这类题目不会让你去实现一个具体的“奇怪函数”，而是要求你分析这个函数在特定数学定义下的行为，并高效计算出它在某个范围内的取值之和或满足某些条件的个数。核心的挑战在于，直接模拟计算在数据范围（n可能高达10^16）下是完全不可行的，必须依靠深刻的数学洞察力，将问题转化为关于最小公倍数（LCM）和容斥原理（Inclusion-Exclusion Principle）的模型。今天，我们就来彻底拆解这道题背后的思维链条，不仅搞懂怎么做，更要弄明白为什么这么做，以及如何将这种“数论+组合”的思维模式应用到更广泛的场景中。

2. 问题核心定义与暴力解法的不可行性

2.1 “奇怪函数” f(i) 的数学定义

题目通常会这样定义函数 f(i)：对于正整数 i，f(i) 等于最小的正整数 x，使得 x 不是 i 的约数。换句话说，我们从1开始逐个检查正整数，第一个不能整除 i 的数就是 f(i) 的值。

我们来举几个例子直观感受一下：

• i = 1: 检查1（1能整除1），检查2（2不能整除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) 对某个大质数（如1e9+7）取模的结果，其中 n 可以非常大。

2.2 为什么不能暴力计算？

最朴素的想法是写一个循环，对每个 i 从1到n，再内层循环从1开始找第一个不能整除 i 的 x，累加 f(i)。我们来简单估算一下复杂度。对于每个 i，寻找 f(i) 平均可能需要 O(sqrt(i)) 次检查（因为一个数的约数大约在这个数量级）。那么总复杂度就是 O(n * sqrt(n))。当 n=10^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，则意味着：

1. i 是 L(x-1) 的倍数（因为1到x-1都能整除i）。
2. i 不是 L(x) 的倍数（如果i是L(x)的倍数，那么x也能整除i，这与f(i)=x矛盾）。

这个观察是解决问题的基石。它将一个关于“整除性”的函数求值问题，转化为了一个关于“最小公倍数倍数”的计数问题。

3. 核心思路转化：从求值到计数

3.1 建立数学模型

根据上面的观察，对于给定的 x（x >= 2），哪些 i 会满足 f(i) = x 呢？

• 条件A：i 是 L(x-1) 的倍数。
• 条件B：i 不是 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) = Σ_{x=2}^{∞} [ 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) = 1
• L(2) = lcm(1,2) = 2
• L(3) = lcm(2,3) = 6
• L(4) = lcm(6,4) = 12
• L(5) = lcm(12,5) = 60
• L(6) = lcm(60,6) = 60
• L(7) = lcm(60,7) = 420
• ...

可以观察到，L(k) 在 k 是质数或质数幂时会显著增长。实际上，L(k) 约等于 e^{k(1+o(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 算法流程

1. 预处理 L 数组：计算 L(1), L(2), ..., L(K)。其中 K 是一个足够大的数，确保 L(K) > n（例如取K=60）。计算 L(k) 可以用递推：L(k) = lcm(L(k-1), k)。
2. 初始化答案：ans = 0。
3. 枚举 x 进行求和：for x from 2 to K:。
   • 计算term = (n // L(x-1) - n // L(x)) % MOD。这里//表示整数除法（floor）。
   • 将贡献加入答案：ans = (ans + x * term) % MOD。
4. 输出答案：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，就可以停止，因为对于更大的 k，L(k-1) >= l[k] > n，floor(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 | 1<=i<=n, i % L(x-1) == 0 }，大小|A| = floor(n / L(x-1))。
• 集合 B：{ i | 1<=i<=n, 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 以 n=10 为例进行演算

让我们手动计算 S(10) 来验证思路。 首先列出 L(k):

• L(1)=1, L(2)=2, L(3)=6, L(4)=12, L(5)=60, L(6)=60...

现在枚举 x:

• x=2: count = floor(10/L(1)) - floor(10/L(2)) = 10/1 - 10/2 = 10 - 5 = 5。贡献 2*5=10。 （验证：i=1,3,5,7,9 的 f(i) 都是2，共5个）
• x=3: count = floor(10/L(2)) - floor(10/L(3)) = 5 - floor(10/6)=5-1=4。贡献 3*4=12。 （验证：i=2,4,8,10 的 f(i) 都是3，共4个）
• x=4: count = floor(10/L(3)) - floor(10/L(4)) = 1 - floor(10/12)=1-0=1。贡献 4*1=4。 （验证：i=6 的 f(i)=4，共1个）
• x=5: 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。 后续 x>=5 时，因为 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。求和 2+3+2+3+2+4+2+3+2+3 = 26。完全正确。

5.2 算法复杂度分析

• 时间复杂度：预处理 LCM 数组需要 O(K) 次运算，其中 K 是满足 L(K) > n 的最小整数，大约在 log(n) 级别，但更准确地说是 O(几十)。求和循环也是 O(K)。因此总时间复杂度为 O(K)，对于 n<=10^16，K~50-60，是常数时间。
• 空间复杂度：只需要存储长度为 O(K) 的 LCM 数组，是常数空间。

5.3 边界条件与陷阱

1. x 的起始值：f(i) 的最小值是2（当 i 是奇数时），所以我们的求和从 x=2 开始。公式中使用了 L(x-1)，因此需要定义好 L(1)=1。
2. 大数取模：题目通常要求对一个大质数（如1e9+7）取模。在计算count * x时，count可能很大（最大可达 n），x最大为 K。直接相乘可能超出64位整数范围（在C++中），需要在乘法前后及时取模，或者使用__int128。
3. LCM 的计算效率：计算 lcm(a, b) 时，使用公式a / gcd(a,b) * b。注意计算顺序，先做除法再做乘法，避免中间结果溢出。在预处理时，如果发现l[k-1] / gcd * k > n，我们可以直接设置l[k] = n+1或一个大于 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) = x（x给定）。这就是我们推导过程中的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，我们仍然需要从 x=2 开始求和，直到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 错误类型汇总

1. LCM计算溢出：在C++中使用lcm = a / gcd * b时，a / gcd的结果可能没问题，但乘以b时可能溢出long long。解决方案：提前判断，如果a / gcd > LLONG_MAX / b，则说明会溢出，此时可以直接将 LCM 设为一个大于 n 的哨兵值。
2. 循环终止条件错误：在枚举 x 求和时，不能简单地循环到固定值（比如60），而应该判断L(x-1) <= n作为继续循环的条件。否则当 n 很小时会做很多无用功，虽然不影响结果，但不优雅。
3. 取模错误：count = (n / L(x-1) - n / L(x))这个差值可能为负数吗？不会，因为L(x)是L(x-1)的倍数，所以n / L(x-1)一定大于等于n / L(x)。但在编程中，由于是整数除法，确保使用无符号整数或确保结果非负即可。
4. 忽略 f(i) 的最小值：有的同学可能从 x=1 开始枚举。但 f(i) 最小为2，所以 x 应从2开始。从1开始会导致多算一项（x=1），且 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） vector<ll> 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) 级别（实际上是常数）的优雅解法。这道题完美地展示了数论和组合思维在算法竞赛中的威力。

更深层的启示：

1. 关注函数的“逆问题”：与其思考给定 i 求 f(i)，不如思考给定值 x，哪些 i 能满足 f(i)=x。这种“求逆”或“分类讨论”的思想是组合计数的核心。
2. 寻找不变量和快速增长量：LCM 函数的爆炸性增长是我们能够大幅减少枚举范围的关键。在算法设计中，寻找那些随参数增长极快的量，往往是优化复杂度的突破口。
3. 容斥原理的灵活运用：本题只用到了两个集合的简单容斥，但其思想是普适的。对于更复杂的条件（如“能被a或b整除”、“不能被a且不能被b整除”），容斥原理是系统化计数的标准工具。

最后，虽然这道题背景是竞赛，但其中蕴含的“转化问题”、“批量计数”、“利用数学性质简化计算”的思想，在软件开发、数据分析甚至理论研究中都时有体现。下次当你遇到一个需要遍历大量数据求某个函数和的问题时，不妨停下来想一想：这个函数值背后，是否隐藏着可以批量归类的数学结构？