别再用暴力枚举了！PTA L1-006连续因子题，用数学优化把复杂度降下来

突破暴力枚举：用数学思维优化连续因子搜索算法

每次看到PTA天梯赛L1-006连续因子这道题，总让我想起初学算法时被暴力枚举支配的恐惧。当时我花了整整一个下午调试双重循环，结果提交后还是因为超时被系统无情拒绝。直到后来掌握了数学优化技巧，才发现原来这道题可以如此优雅地解决。今天，我们就来彻底剖析这道经典题目，看看如何用数学性质将时间复杂度从O(n²)降到O(√n)，甚至在某些情况下达到接近O(1)的效果。

1. 问题本质与暴力解法的局限

连续因子问题要求我们找到一个正整数N的最长连续整数序列，这些整数的乘积能整除N。表面看这是个简单的枚举问题，但魔鬼藏在细节里——当N接近2³¹时，传统暴力方法的性能瓶颈就暴露无遗。

典型的双重循环解法是这样的：

for (int len = max_len; len >= 1; len--) { for (int start = 2; start + len - 1 <= N; start++) { int product = 1; for (int i = start; i < start + len; i++) { product *= i; } if (N % product == 0) { // 找到解 } } }

这种解法有三重循环，最坏时间复杂度达到O(n³)。即使优化掉最内层的乘积计算，也仍有O(n²)的复杂度。当N=2³¹-1时，这样的算法在OJ系统上必然超时。

关键观察：连续整数的乘积增长速度极快。12!就已经大于2³¹，这意味着我们实际需要检查的连续序列长度不会超过12。

2. 数学优化：缩小搜索空间的三大策略

2.1 因子范围的精确控制

数学告诉我们，任何合数N的因子都不会超过√N。这立即将我们的搜索范围从O(n)缩小到O(√n)。但我们可以做得更好：

1. 质数优先检查：如果N是质数，解就是N本身
2. 因子连续性分析：连续因子的乘积必须整除N
3. 乘积增长特性：连续数字的乘积呈阶乘式增长

bool is_prime(unsigned int n) { if (n <= 1) return false; for (unsigned int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; }

2.2 连续序列长度的数学上界

通过数学分析可以确定最大可能长度L满足：

L! ≤ N < (L+1)!

对于不同的N范围，L的最大值如下表所示：

这个表告诉我们，实际需要检查的序列长度非常有限，完全不需要从N开始倒序枚举。

2.3 滑动窗口与乘积优化

我们可以采用滑动窗口技术，动态维护当前连续因子的乘积：

1. 初始化窗口[start, end]，乘积product=1
2. 扩展窗口：end++，product *= end
3. 当product > N时，收缩窗口：product /= start，start++
4. 当N % product == 0时，记录当前窗口

这种方法将时间复杂度优化到O(L√N)，其中L是最大可能长度，通常不超过12。

3. 最优解法实现与性能对比

结合上述优化，我们得到最终的高效解法：

#include <iostream> #include <vector> using namespace std; vector<int> findContinuousFactors(unsigned int N) { if (is_prime(N)) return {N}; int max_len = 0; int best_start = 0; for (int len = 12; len >= 1; len--) { for (int start = 2; start + len - 1 <= sqrt(N) + 1; start++) { long long product = 1; for (int i = start; i < start + len; i++) { product *= i; if (product > N) break; } if (product <= N && N % product == 0) { if (len > max_len) { max_len = len; best_start = start; } } } if (max_len != 0) break; // 找到最长解立即返回 } vector<int> result; for (int i = 0; i < max_len; i++) { result.push_back(best_start + i); } return result; }

性能对比表：

4. 边界条件与特殊案例处理

在实际编码中，有几个关键边界条件需要特别注意：

1. 质数处理：当N是质数时，直接返回[N]
2. 大数溢出：使用long long存储中间乘积
3. 相同长度序列：选择起始数字最小的序列
4. 1的特殊情况：题目明确要求1不算在因子内

测试案例大全：

在解决这道题的过程中，最让我印象深刻的是处理N=362880这个案例。最初我的代码在找到234后就停止了，忽略了更长的678910。这提醒我，在算法设计中，理论分析必须与实际情况紧密结合，任何假设都需要用测试案例验证。