从一道蓝桥杯题说起

蓝桥杯的填空题里有一类题长这样：

【问题描述】
在 1 到 N 之间，有多少个奇数的平方不超过 N？

【输入格式】
输入一行，包含一个正整数 N。

【输出格式】
输出一行，包含一个整数，表示答案。

【样例输入】
100

【样例输出】
5

【评测用例规模与约定】
对于 60% 的评测用例，1 ≤ N ≤ 10^6；
对于所有评测用例，1 ≤ N ≤ 10^9。

样例只有一行输入、一个输出，看起来比课本里的习题还简单。真正决定这道题难度的是最后两行——N 最大可以到 10^9。这节课要回答的问题就是：末两行为什么能决定一道题的难度。

从问题到程序的四步

拿到上面的题面，要到一份能提交的代码，中间有四步。

第一步，读清楚问题。 题目问的是"奇数 k 的平方不超过 N"的 k 有几个，不是求这些平方的和，也不是求奇数本身的个数。第一遍读题时把"多少"读成"哪些"、把"不超过"读成"小于"，都是常事。

第二步，想清楚输入和输出。 输入是一行一个正整数 N，输出是一行一个整数。程序从标准输入读、往标准输出写——蓝桥杯的评测机就是把输入喂进来、拿走输出，跟样例里的样子一致。

第三步，处理。 把"符合条件的有几个"变成一串能执行的动作：从 k = 1 开始一个个试，k 平方不超过 N 就计数加一，超过就停。

第四步，输出。 把计数结果打印出来。

这四步里，第三步是后面每一课要反复练的地方，前两步出错则整道题白做。一种常见的翻车方式是：程序算得又快又对，只是输出多了一行"答案是："。评测机拿它跟标准答案逐字比对，判零分。判题程序不知道你的提示文字有什么意义，它只比较两份文本。

算法是什么

"算法"这个词来自 9 世纪的波斯数学家花拉子米（al-Khwarizmi）名字的拉丁化写法 algorismus，最初指的就是用阿拉伯数字做算术的那套笔算步骤。这里的"步骤"包含三层要求：

• 有限：执行必须在有限步之内停下。一直循环下去不叫算法，叫死循环。
• 确定：每一步做什么是明确规定的。同一个输入跑两遍，必须得到同一个结果；"凭感觉调一下"不算步骤。
• 有输入、有输出：给定合法输入，必然产出结果。

把这三条合起来：算法是解决某一类问题的一套有限、确定的步骤，给定合法输入，按步骤执行必然在有限步内停下并产出结果。 上面的循环求和是一个算法，while True: pass 不是。

按照这个定义，覆盖 10^9 的暴力枚举仍然是算法——它有限、确定，也能产出结果。速度不在这三条要求里，它由评测用例的时限决定：考试只给你一秒或两秒，跑不完的算法就得换掉。

数据规模决定可行性

同一道题，评测用例分档，我们可以把最容易想到的写法（后面统一叫暴力解：不做优化、按定义直接枚举所有可能）拿来分别试。

题面里的 N 有一个数据范围，正是它决定了这个算法能不能跑完。有一道同样说法的题：求 1 + 2 + \dots + N。最容易想到的写法是把 1 到 N 逐个加起来：

n = int(input())
total = 0
for i in range(1, n + 1):
    total += i
print(total)

这段代码只有五行。把 n 换成不同的值，在这台机器上跑出来的结果是：

每放大十倍规模，耗时也大约放大十倍，这正是我们期望的规律。可问题就在这个规律上：按这个比例，n = 10^9 要跑大约 19 秒，蓝桥杯的 1 秒时限连零头都不够。

再过一遍这段代码的每一步：total += i 是一次加法，range 每轮给出一个 i。整个循环执行了 n 次加法，所以耗时正比于 n——循环次数与耗时成正比，这就是耗时随规模线性增长的原因。

换个思路，这件事其实可以不算那么多次。退一步回到小学奥数就知道的结论：1 + 2 + \dots + n = \dfrac{n(n+1)}{2}。用这个公式，n 取多大都只做几次乘除：

n = int(input())
print(n * (n + 1) // 2)

在这台机器上，这一行代码无论 n 取 10^6 还是 10^9，耗时都在微秒量级（三次测量取最小值 0.2 微秒）。和循环的 10^9 次加法相比，差了若干数量级，被测代码本身的耗时已经和测量误差一个量级。

两个算法的答案一样，耗时却差出几个数量级，差别的来源是基本操作的次数：循环要执行 n 次，公式只执行固定几次，两种写法的操作次数随 n 增长的趋势完全不同。这里用的是 OI Wiki 给出的尺子——实际用时依赖机器、难以在理论上计算，实际测量又麻烦，所以衡量算法效率时数的通常不是秒，而是算法需要执行的基本操作数量。

写之前先估一下

看两道改过的题。

第一道：1 \le N \le 10^6，求 1 + 2 + \dots + N。循环要跑 10^6 次，按上面的实测约 19 毫秒，写循环就够了。

第二道：1 \le N \le 10^9，同样的式子。循环要跑 10^9 次，按实测比例推是 19 秒，交上去等来的会是"运行超时"。这时得换做法，把结论直接算出来，而不是逐项累加——比如奇数求和 1 + 3 + \dots + (2m-1) = m^2：它的操作次数不随 N 增长，N 取多大都只做几次乘除。回顾开头那道填空题，N 取 10^9 时的答案也是同一个道理算出来的：先由 k^2 \le N 定出上界 k \le 31622，再数一数这个范围内有多少个奇数，答案是 15811。

真正的坑在第一步：这两道题看着是同一句话，代码也几乎一样，数据范围只差三个数量级。样例永远只有三五个数，永远跑得飞快，所以"样例通过了"这句话对评测结果几乎没有预测力——提交前该做的判断是"我的循环会跑多少次、跑到 10^9 还能不能在一秒内跑完"，而这个判断在写代码之前就可以做完。 从下一课起，我们会把它练成一套固定的算法：看数据范围、估操作次数、定复杂度上限。

练习

500000500000

import timeit

def loop_sum(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

for n in (10**5, 10**6, 10**7):
    t = min(timeit.repeat(lambda: loop_sum(n), number=1, repeat=5))
    print(n, f"{t:.4f} 秒")

这一课用到的 Python

后面每一课都会用到 for、range、变量和输入输出，这里把它们的最小用法对一遍。

课程后面会把这套写法整理成函数——重复出现的处理步骤打包成一个有名字的代码块，调用一次就执行一遍。这一步先不展开，眼下循环和缩进够用了。

这门课最后会做出什么

这门课的检验手段是蓝桥杯真题：真实的数据范围、真实的时限、以及"你到底会不会"的诚实反馈。目标是把原理和复杂度吃透到能讲给别人听的深度，所以后面每一课都会走完"提问题、写代码、估复杂度、验证"这一整套，而不只是背下模板。

配套项目是一个「AI 刷题助手」：输入一段题目文本，由大模型辅助分析题意、给出候选算法，再用对拍器与样例自动验证候选解。它会在这门课的实验课里一段一段长出来——从这一课开始，你练的每一步都是它的一部分。

• OI Wiki · 复杂度复杂度定义、渐进符号与「数据规模 ↔ 可接受复杂度」的对照，本课"数操作次数"的口径出自这里
• Python 官方文档 · timeit性能测量的官方用法，练习第二步照它写
• 《Python 编程：从入门到实践（第 2 版）》第 4 章 操作列表用循环处理一批数据的写法，本地教材