第一次在洛谷题库里遇到 P1035 级数求和很多人第一反应是“级数是不是要用数学公式瞬间求出答案”等真正打开题目才发现题干短得可怜已知 S_n 1 1/2 1/3 … 1/n给定整数 K求最小的 n 使 S_n K。作为 NOIP 2002 普及组的经典题它被收录在洛谷题库 P1035网上题解五花八门有人直接用 double 暴力过题有人特意强调浮点精度陷阱还有人干脆离线打表。这道题到底在考什么其实考的是三件小事理解“级数”概念、判断枚举是否可行、以及处理浮点数累加时的边界问题。这篇文章我会从题意拆解、暴力思路、三种语言实现、精度陷阱、数学背景一路讲到进阶扩展把这道入门级送分题彻底吃透。1. 题目到底在问什么逐字拆解与数据范围理解1.1 题干翻译成人话原题出自 NOIP 2002 普及组洛谷编号 P1035。题干大意是已知 S_n 1 1/2 1/3 … 1/n。显然对于任意整数 K当 n 足够大时S_n 大于 K。现给出一个整数 K1 ≤ K ≤ 15要求计算出一个最小的 n使得 S_n K。翻译成正常人能听懂的话从 1 开始依次把 1、1/2、1/3、1/4……累加起来每加一项看一次总和当总和第一次超过 K 的时候停下手数一数自己到底加了多少项这个项数就是答案。举个例子K 1 时n 1S_1 11 并不大于 1n 2S_2 1 1/2 1.51.5 1所以最小 n 是 2。题目只给一个整数 K输出一个整数 n。输入输出格式简单没有多组数据没有取模没有字符串处理。对很多刚接触信息学奥赛的人来说这道题特别适合作为“入坑第一道题”它把“读题、分析规模、写循环、交题”这套完整流程都训练了一遍。1.2 数据范围告诉你什么最大的隐藏信息藏在这个看似不起眼的边界里K 最大只有 15。很多新手会想“1 1/2 1/3 … 加十五层不就超过 15 了吗”事实完全相反。这个级数增长慢得吓人。我直接列一张表把每个 K 对应的最小 n 写出来你看完就明白了K最小的 n备注12S_2 1.524S_4 ≈ 2.0833311S_11 ≈ 3.0199431增长明显变慢5836227761681674945501012367113361712913801324839714675214151835421n 已经到百万量级看到没有为了超过 15居然要累加接近 184 万项。正因为 K ≤ 15n 的最大值大约只有 183 万这意味着一个简单的循环完全可以在时间限制内跑完。同时1835421 这个数量级也告诉我们答案是 int 范围内的小数字输出、存储、计算都没有压力。题目设计成这样就是想让你用一个最直接的枚举循环去解决不需要任何高级数据结构。2. 解题思路为什么暴力枚举是这道题的最优解2.1 调和级数增长到底有多慢1 1/2 1/3 … 1/n 在数学上叫调和级数记作 H_n。它的每一项都在变小但总和却会一直变大最终趋向无穷大这就是“发散”。可它发散的速度慢到反直觉约等于自然对数 ln(n) 再加上一个常数。用生活类比来解释如果每天给你一块钱但是第二天只给五毛第三天只给三毛三第四天只给两毛五……你以为很快就能攒到 100 块实际攒到 15 块就要接近 200 万天换算成年份超过 5000 年。这就是调和级数给你的直觉冲击。这个特性直接决定了算法选择循环次数虽然达到百万级但完全可控。K 15 时循环 183 万次C 在 1 毫秒左右跑完Python 也就 0.1 秒左右连优化都不用做。2.2 枚举的复杂度分析时间复杂度是 O(n)其中 n 是答案本质上等于 e^(K) 级别的增长。因为 K ≤ 15n 最多 183 万这个复杂度在绝大多数在线评测系统上都稳如泰山。空间复杂度更不用说只需要一个 double 变量和一个 int 计数器O(1)。很多刚入门的朋友容易陷入一个误区一看到“级数求和”就觉得应该套公式。比如想到调和级数近似公式 H_n ≈ ln(n) γ然后试图直接解方程。实际上这个公式只是近似要拿它精确判定边界反而还得配合浮点误差分析比暴力循环麻烦得多。在数据范围明确允许枚举的时候直接枚举就是最优解。竞赛里有一句话很实在“先写能过题的最简单代码再考虑优化。”这道题的最简单代码就是 while 循环。2.3 为什么不需要二分、前缀和或打表理论上我们可以二分查找最小的 n让 H_n K但前提是能快速计算 H_mid。如果每次二分都临时从 1 加到 mid单次计算就是 O(mid)整体复杂度反而退化。如果预处理前缀和那本质还是把每个 H_i 算了一遍和暴力没有区别。所以二分方案在这道题里没有意义。打表倒是可行因为 K 只有 1 到 15 共 15 种输入完全可以把上面那张表硬编码进程序输入 K 直接输出对应 n。洛谷上提交打表代码一般也能 AC但我不建议初学者这么干。打表绕过了核心训练目标而且一旦题目改成多组询问K 范围扩大你又会陷入被动。正确顺序是先用最简单的枚举把题做对再回头看数学原理最后才考虑有没有更优雅的优化。对这道题而言暴力本身就是最优解。3. 三种语言实现与逐行复盘3.1 C 版本直接给出最稳的写法#include iostream using namespace std; int main() { int k; cin k; double s 0.0; int n 0; while (s k) { n; s 1.0 / n; } cout n endl; return 0; }逐行解读一下定义s记录当前总和初始为 0定义n记录当前项数初始为 0while (s k)表示只要还没超过 K就继续累加循环体里先n这样第一轮加的是1.0 / 1第二轮加的是1.0 / 2完全符合题意退出循环时一定满足s k这时的 n 就是答案。这里最关键的细节是1.0 / n不是1 / n。在 C 里整数除以整数得到的是整数1 / n在 n 1 时全部等于 0一旦写成这样循环就永远不会退出直接超时。这个坑我见过无数人踩。还可以换一种写法#include iostream using namespace std; int main() { int k; cin k; double s 0.0; for (int i 1; ; i) { s 1.0 / i; if (s k) { cout i endl; break; } } return 0; }这种写法把“先累加再判断”的语义表达得更直接。两种写法都能 AC看你个人习惯。我个人更喜欢第二种因为循环变量 i 就是当前项数不需要额外维护 n。3.2 Python 版本Python 的写法同样简洁k int(input()) s 0.0 n 0 while s k: n 1 s 1.0 / n print(n)Python 3 里/默认就是浮点除法所以写1 / n也能得到浮点数但为了风格统一和防止有人用 Python 2 跑建议还是写1.0 / n。另外注意int(input())读入的是一个整数不写 int 的话 k 是字符串和浮点数比较会直接报错。Python 代码在洛谷上跑这道题一点压力也没有K 15 时大约 0.1 到 0.2 秒。如果你担心速度交 PyPy 也可以。3.3 Java 版本import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int k sc.nextInt(); double s 0.0; int n 0; while (s k) { n; s 1.0 / n; } System.out.println(n); } }洛谷要求 Java 主类名必须是Main类名写错会编译失败。程序逻辑和 C 完全一样1.0 / n会把 n 先转成 double 再相除得到浮点数。Java 在这道题上的执行速度也不错183 万次浮点加法大概几十毫秒完全不用担心。3.4 代码风格与技术选型的个人建议不要用float用double。float 只有约 7 位十进制有效数字180 万次累加后误差虽然很小但 double 更稳误差大约 1e-10 级别远不足以影响和整数 K 的比较。不要在循环体里写cout s去调试。新手经常这么干一旦忘记删除输出几百行调试信息白白罚时。如果可以本地多测几组数据再提交特别是 K 15 这种边界值。4. 精度陷阱与边界测试最容易翻车的几个地方4.1 整数除法把 1/n 清零我反复强调1.0 / n因为它确实是最常见的错误点。C、C、Java 里1 / n做的是整数除法。n 2 时结果是 0n 3 时结果还是 0。如果你不小心写成s 1 / n那么 s 永远等于 0while 条件永远成立程序陷入死循环。最后你看到的不是 WA而是 TLE。解决方法无非两点一是分子写成1.0二是把 n 转成浮点数再做除法。这个错误看起来蠢但每年都有大量新手栽在上面。刷完这道题你最好养成一个习惯写浮点除法的时候先看一眼分子分母是不是都是整数。4.2 double 精度到底够不够有人担心183 万次累加double 会不会产生明显误差我们来想一下。double 在计算机里用 53 位二进制有效数字表示数值大约对应 15 到 16 位十进制有效数字。每次1.0 / n的计算本身有舍入误差累加 183 万次后误差会累积但这个累积值通常在 1e-10 量级甚至更小。而我们要和整数 K最大 15比较中间差了至少约 1 个单位的“安全距离”所以 double 的判断结果完全可信。float 其实也未必会错因为同样有大约 1e-5 级别的误差离整数边界很远。但竞赛环境里没必要赌这种精度直接用 double 是行业共识。有一种情况需要特别注意如果以后遇到需要判断两个浮点数是否相等的题千万别直接写if (a b)应该用fabs(a - b) eps。虽然本题用不到但这是刷浮点题必须养成的意识。4.3 比较符号用 还是 题目要求的是 S_n K所以循环退出条件应该是“当前总和已经严格大于 K”。用代码表达就是while (s k) { // 继续累加 }退出循环时必然满足 s k。如果写成while (s k)会怎样考虑 K 1 的情况n 1累加后 s 1此时如果条件是s k那么 1 1 为假循环退出输出 n 1但 S_1 1并不满足“大于 1”正确答案是 2。这就直接 WA 了。所以必须写把“相等”这种情况留给循环继续处理。当然实际数据里除了 K 1 以外其他 K 对应的 S_n 几乎不可能是整数但你不能赌“几乎”。4.4 用边界数据做自测提交前至少测两个数据K 1 和 K 15。K 1 应该输出 2这是最简单的边界检查能同时暴露你的循环结构和比较符号有没有问题。K 15 应该输出 1835421。如果你看到这个数字说明浮点累加和循环次数都正常。如果输出的是 1835420 或者 1835422多半是精度或者边界判断出了问题。我把每个 K 对应的最小 n 再贴一次方便你做本地对拍K答案 n122431143158362277616816749455010123671133617129138013248397146752141518354215. 调和级数的数学背景欧拉常数与答案估算5.1 调和级数为什么发散有人会问1/n 不是趋近于 0 吗为什么所有项加起来能超过任意大的 K这正是调和级数反直觉的地方。数学上有一个经典的“分组证明”把 1/n 按 1、1/2、1/31/4、1/5...1/8 这样分组每组都大于等于 1/2。第一组 1 就不说了第二组是 1/2第三组 1/3 1/4 1/2第四组 1/5 1/6 1/7 1/8 4 × 1/8 1/2。无限组下来和自然趋于无穷大。这就说明虽然每一项都小但“小项无限堆叠”也能堆出无限大的总和。理解这个性质对做本题很有帮助你已经知道答案一定存在不需要担心循环找不到 n 而陷入死循环。从编程角度讲这道题不会出现无解情况也是它作为入门题友好的一面。5.2 欧拉常数与渐近展开调和级数还有一个更精确的近似公式H_n ln(n) γ 1/(2n) - 1/(12n²) …其中 γ 是欧拉常数约等于 0.5772156649。当 n 很大时误差项越来越小我们可以用 ln(n) γ 来近似 H_n。利用这个公式给定 K估计满足 H_n K 的最小 nn ≈ e^(K - γ)。代入 K 15可以估算出 n ≈ e^(15 - 0.5772) e^14.4228 ≈ 183.5 万。这和真实答案 1835421 非常接近误差在个位数到百位数的级别。这就是数学估算的威力。但注意这只是估算。它告诉你答案的量级但要在竞赛里拿到精确答案仍然需要枚举验证。你可以用它来预先判断“暴力循环需要跑多少次”而不是直接把它当结论输出。5.3 估算技巧在比赛里的实际用途第一写代码前看规模。以后遇到任何循环题先估算答案量级如果答案是 e^(20) 这种天文数字暴力基本必超时如果答案是百万级暴力就非常安全。第二用来对拍。你可以先用估算公式算出一个“大概的 n”再用程序精确枚举看看两者是否一致。如果差得很远说明你的程序逻辑或浮点精度出问题了。这种“理论预估 枚举验证”的双保险思路在信息学竞赛里非常实用。第三理解数据范围设计的用心。K ≤ 15 不是随便给的它保证枚举答案在 int 范围内也让浮点误差可控。看到这个限制你就应该毫不犹豫选暴力。5.4 离线打表是不是一种“作弊”前面提到过打表可以 AC这里展开讲一下。因为 K 只有 15 个可能取值你完全可以先本地跑一遍得到答案数组然后提交如下代码int ans[16] {0, 2, 4, 11, 31, 83, 227, 616, 1674, 4550, 12367, 33617, 91380, 248397, 675214, 1835421}; int k; cin k; cout ans[k] endl;这代码时间复杂度 O(1)绝对能过。但我不推荐初学者这么做原因有两点你绕开了这道题最核心的“模拟累加”训练丢了练习机会如果题目数据范围一改比如 K 变成 10^9 且多组询问打表思路立刻失效而循环枚举作为基础能力却永远不过时。真正合理的做法是先会写暴力再把打表作为一种补充技巧。当你暴力代码已经 AC 之后想研究一下离线打表怎么实现那完全没问题。6. 从普及组到进阶这道题还能带给你什么6.1 先看数据范围再决定算法这道题最大的教育意义是强迫你形成“规模感知”。很多新手拿到题第一件事就是套模板看到“求和”就考虑前缀和看到“最小”就考虑二分结果绕了一大圈。正确的顺序应该是看 K ≤ 15估算答案最大 1835421判断枚举能不能过能过就直接写只有枚举明显超时才去考虑优化算法。这道题就是把“先暴力再优化”的思维方式刻进你脑子里。以后遇到 P 系列普及组题目很多都可以先写暴力保底再逐步优化拿满分。6.2 如果 K 变大该怎么办作为扩展假设题目把 K 放大到 20甚至 30暴力循环还可行吗K 20 时最小 n 大约是 e^(19.42) ≈ 2.7 亿。C 跑 2.7 亿次浮点加法还有希望在 1 秒左右通过Python 基本没戏。K 30 时n 大约是 6 万亿次再强的 O(n) 枚举都不可能通过。这时候就需要更高级的手法二分 调和级数渐近公式。先用近似公式算出 n 的大概区间再二分定位最后在小范围内枚举校准。这就是“数学优化”与“算法”结合的典型思路。不过我要提醒一句那是后面的学习内容。你现在只需要知道暴力有边界数学知识能帮你突破边界而突破边界之前先把边界内的暴力写得又对又稳。6.3 类似题目的刷题建议如果你觉得这道题太简单想趁热打铁可以试试洛谷里这些同类入门题P1009 [NOIP 1998 普及组] 阶乘之和同样是累加问题但引入了高精度难度上升一个台阶P1115 最大子段和教你“枚举子段”会超时必须用前缀和或动态规划P1308 统计单词数字符串处理入门注意力全在边界条件上。这些题放在一起刷你会明显感觉到“读懂数据范围”这件事有多重要。每道看似简单的普及组题背后其实都藏着对某一种基本能力的刻意训练。6.4 我在实操里的一点体会带新手刷题这几年我发现 P1035 真正筛掉人的不是算法而是几个不起眼的细节1.0 / n写没写对用没用对K 15 之前有没有自测过。一旦这三件事都做到这道题就是标准的保送题。我个人习惯是刷这种浮点累加题时把所有输出都先往一个 volatile double 里塞一遍再比较退出条件虽然有点强迫症但确实少踩很多精度的坑。你不需要学我这个习惯但一定要学“边界自测”的意识。洛谷 P1035 级数求和是我心里最适合作为 OI 入门教学样例的题目之一代码短、坑点多、数学背景丰富、扩展空间大。把它彻底弄明白你的普及组基础就算打牢了一块。