1. 从一道省赛题说起平方差问题的本质拆解第一次看到“平方差”这三个字很多人的直觉反应是初中代数里的那个公式a² - b² (ab)(a-b)。这道题把这个公式搬到了算法竞赛的语境里问的其实是另一件事——给定一个区间 [L, R]统计这个区间内有多少个整数能够表示成两个整数的平方差。标题里提到的“打表前缀和”就是解决这类区间统计问题的经典组合拳而 Python 在这里的角色是快速验证思路、生成规律、辅助推导的工具。我先把这个问题的核心说清楚。一个整数 N 能不能写成 x² - y² 的形式其中 x、y 是整数注意题目通常允许 y 为 0 或负数但平方之后效果一样所以本质上只关心非负整数。用公式展开N (xy)(x-y)。令 a xyb x-y那么 a 和 b 的奇偶性必须相同因为它们的和是 2x差是 2y都是偶数且 a·b N。这就引出了一个非常干净的结论一个数能表示成平方差当且仅当它不是形如 4k2 的数。换句话说所有奇数都可以取 b1aN所有 4 的倍数也可以取 aN/2b2 这类构造唯独除以 4 余 2 的数不行。这个结论是整道题的基石。我在实际推导时习惯先用小范围暴力枚举验证一遍确认规律无误再上大范围。比如 N1 可以1²-0²N2 不行N3 可以2²-1²N4 可以2²-0²N5 可以3²-2²N6 不行N7 可以N8 可以3²-1²N9 可以N10 不行……规律非常稳定每隔四个数就有两个“不行”的准确说是所有 4k2 形式的数被排除。标题里“打表前缀和”的思路正是基于这个结论做区间计数。打表的意思是预先算出每个位置上的“可行标记”前缀和则是把“区间内有多少个可行数”这个问题转化成两个前缀值相减。这套方法在区间统计类题目里几乎是万能模板值得吃透。适合谁来读这篇内容如果你正在准备蓝桥杯这类算法竞赛或者想理解“数学结论预处理区间查询”这套组合思路下面的拆解应该能帮到你。哪怕你只是刚学 Python、想找个练手项目这个题目的规模也足够小不会一上来就被复杂度吓退。2. 为什么选打表加前缀和方案选型背后的取舍2.1 暴力枚举为什么不够用最直接的做法是对区间 [L, R] 里的每个数 N枚举 x 和 y 看能不能凑出平方差。但 x 和 y 的范围怎么定理论上 x 可以大到 sqrt(N y²)枚举量随 N 增长而膨胀。如果查询次数多、区间又大这种逐个数逐对枚举的方式会直接超时。更关键的是暴力枚举没有利用“平方差可行性”的数学结构等于把一道有闭式结论的题当成了搜索题来做方向就偏了。我在早期练习时踩过这个坑看到“平方差”就去写双重循环枚举 x、y小数据能过一到大区间就卡死。后来才意识到这类“统计满足某性质的数的个数”问题只要性质本身可以 O(1) 判定就应该把重心放在“如何快速回答区间查询”上而不是“如何快速判定单个数”。判定单个数用数学结论一秒出结果剩下的就是区间统计的工程问题。2.2 打表加前缀和的分工逻辑打表和前缀和是两个层次的东西得分开理解。打表解决的是“每个位置是否可行”的判定问题把数学结论固化成一张布尔表或标记数组前缀和解决的是“区间内可行数有多少”的聚合问题把区间求和转化成两个端点前缀值的差。两者结合单次查询的复杂度降到 O(1)预处理是 O(n)。这个分工的好处在于职责清晰。判定逻辑是不是 4k2只写一次放在打表阶段查询逻辑区间相减也只写一次放在前缀和阶段。后续如果题目性质变了比如改成“统计平方和”或者别的判定条件只需要替换打表那一段前缀和框架原封不动。这种可替换性是我特别看重的写竞赛代码时结构清晰能省下大量调试时间。2.3 Python 在这个场景里的定位有人会问竞赛题不是应该用 C 吗为什么标题强调 Python我的理解是Python 在这里承担的是“快速原型规律验证”的角色。这道题的核心难点不在性能而在把数学规律找对、把边界处理干净。Python 写起来快交互式环境里随手就能打印前几十项看看规律打表验证的效率极高。真正比赛时如果数据规模极大可以把验证好的逻辑翻译成 C但思路探索阶段用 Python 是明智的。而且这道题的数据范围如果控制在合理区间内Python 的前缀和数组完全跑得动。假设区间上界是 10⁶ 级别一个长度为 10⁶ 的列表做前缀和内存和耗时都在可接受范围。所以“Python 打表前缀和”不是妥协而是针对这个具体问题规模做出的合理选择。选型的关键永远是匹配问题特征而不是盲目追求语言性能。3. 核心细节拆解从数学结论到代码落地3.1 平方差可行性的完整证明思路前面给了结论这里把证明补完整因为理解证明才能处理边界。设 N x² - y² (xy)(x-y)。令 u xyv x-y则 u、v 同奇偶且 N u·v。情况一N 是奇数。取 u Nv 1两者都是奇数同奇偶成立解出 x (N1)/2y (N-1)/2都是整数。所以所有奇数可行。情况二N 是 4 的倍数。取 u N/2v 2。因为 N 是 4 的倍数N/2 是偶数和 v2 同偶成立。解出 x (N/22)/2y (N/2-2)/2都是整数。所以所有 4 的倍数可行。情况三N 形如 4k2。此时 N 是偶数但不是 4 的倍数N 的质因数分解里 2 的指数恰好是 1。若 u·v N 且 u、v 同奇偶则两者要么都是奇数乘积为奇数矛盾要么都是偶数乘积至少含 2²4 的因子矛盾。所以不可行。证明干净利落三种情况覆盖全部整数。落到代码里判定条件就是N % 4 ! 2。这一行就是整个打表的核心。3.2 打表数组的构造与边界处理打表阶段我习惯构造一个标记数组ok[i]表示数字 i 是否可行。但更省事的做法是直接构造前缀和数组跳过单独的标记数组。具体来说令pre[i]表示 1 到 i 之间可行数的个数递推式是pre[i] pre[i-1] (1 if i % 4 ! 2 else 0)。边界要特别注意。如果区间 L 可能为 0 或负数得先确认题目对范围的约定。大多数版本里 L、R 是正整数但稳妥起见我会在代码里对 L 做一次下界保护。另外前缀和数组的下标从 1 开始比较顺手pre[0] 0这样查询 [L, R] 的答案就是pre[R] - pre[L-1]不用额外判断 L 是否为 1。还有一个容易忽略的点打表的上界应该取多少取决于题目给出的 R 的最大值。如果 R 最大到 10⁶就打表到 10⁶如果查询里 R 是动态输入的可以先读入所有查询取最大 R 再打表避免打多了浪费或打少了越界。这个“先读查询再定上界”的技巧在离线查询场景里很实用。3.3 前缀和查询的索引细节前缀和的查询公式看着简单但索引差一错误是新手最容易翻车的地方。pre[R] - pre[L-1]里的L-1必须保证不越界也就是 L 至少为 1。如果 L 可能为 0就得单独处理或者把整个数组整体右移一位让数字 i 对应下标 i1。我个人的习惯是统一用“数字 i 对应下标 i”的映射然后查询时写pre[R] - (pre[L-1] if L 0 else 0)。这样即使 L0 也不会崩。另一种更优雅的做法是让pre数组长度比最大值多 1pre[0]0表示“前 0 个数的前缀和”数字 i 的贡献累加到pre[i]查询 [L,R] 就是pre[R] - pre[L-1]此时要求 L≥1。两种写法都行关键是团队或个人内部保持一致别一半用一种一半用另一种调试时会疯。提示索引映射方式一旦选定就全文统一混用是差一错误的主要来源。4. 完整实操流程从零写出可复现的解法4.1 第一步小范围暴力验证规律动手写正式解法前先花五分钟用暴力法确认规律。思路是对每个 N 从小到大枚举 x 从 0 到某个上界看是否存在 y 使 x²-y²N。Python 里几行就能写完def can_be_diff(n): x 0 while x * x - 0 n 100: # 上界给宽松点 for y in range(x 1): if x * x - y * y n: return True x 1 if x n 10: break return False for n in range(1, 30): print(n, can_be_diff(n), n % 4 ! 2)跑一遍把暴力结果和n % 4 ! 2的判定结果并排打印肉眼扫一遍是否完全一致。这一步看着笨但能极大增强信心也能提前发现题目是否有额外限制比如要求 x、y 为正整数而非非负那结论会变。我见过有人跳过验证直接套结论结果题目要求 y 必须为正导致 N1 这类边界答案出错。验证五分钟省下调试半小时。4.2 第二步构造前缀和数组确认规律后正式构造前缀和。假设题目最大 R 为 MAXR代码如下MAXR 10**6 pre [0] * (MAXR 1) for i in range(1, MAXR 1): pre[i] pre[i - 1] (1 if i % 4 ! 2 else 0)这段代码的时间复杂度 O(MAXR)空间 O(MAXR)。如果 MAXR 到 10⁷Python 的列表会占不少内存每个 int 对象有开销这时候可以考虑用array模块或者干脆换语言。但在 10⁶ 级别普通列表完全够用不必过度优化。构造完之后随手抽查几个值验证pre[4]应该是 31、3、4 可行2 不行pre[8]应该是 6排除 2、6pre[10]应该是 7再排除 10。抽查通过再往下走。4.3 第三步处理多组查询如果题目有多组查询读入后逐组用pre[R] - pre[L-1]回答即可。这里有个性能细节Python 的input()在大批量读入时偏慢建议用sys.stdin一次性读入再切分。查询组数上万时这个差别很明显。import sys def main(): data sys.stdin.read().split() idx 0 t int(data[idx]); idx 1 out [] for _ in range(t): L int(data[idx]); R int(data[idx 1]); idx 2 ans pre[R] - (pre[L - 1] if L 0 else 0) out.append(str(ans)) sys.stdout.write(\n.join(out)) main()把结果攒在列表里最后一次性输出比循环里反复print快得多。这是 Python 竞赛代码的常规操作值得养成习惯。4.4 参数选择与复杂度核算把复杂度算清楚心里才有底。预处理 O(MAXR)单次查询 O(1)总复杂度 O(MAXR Q)其中 Q 是查询组数。空间 O(MAXR)。如果 MAXR10⁶、Q10⁵总操作量约 1.1×10⁶Python 跑下来通常在一秒内安全。如果 MAXR 更大比如 10⁸前缀和数组就吃不消了。这时候要换思路利用“每四个数里恰有两个可行”的周期性直接用公式算区间内可行数个数连打表都省了。公式是区间 [L,R] 内 4k2 形式的数的个数等于count_4k2(R) - count_4k2(L-1)其中count_4k2(n)表示 1 到 n 里形如 4k2 的数的个数可以 O(1) 算出。这个优化方向值得知道但本题规模下打表更直观不必炫技。5. 常见问题与排查技巧实录5.1 差一错误最常见的翻车点排查经验里差一错误占了这类题 bug 的一大半。典型症状是答案整体偏大或偏小固定的量。比如查询 [1,4]正确答案是 3你的代码输出 4多半是pre[R] - pre[L]写成了不减 L-1 而是减 L或者打表时把 i0 也算进去了。排查方法很土但有效手算小范围所有区间的答案和代码输出逐个对比。区间 [1,1]、[1,2]、[2,3]、[3,4] 这几个先过一遍差一错误立刻现形。我习惯在代码里加一个assert做自检正式提交前删掉但调试阶段非常管用。5.2 边界值处理速查表下面这张表把常见边界情况和处理方式列清楚遇到问题直接对照场景风险处理方式L 0pre[L-1]越界判断 L0 再减或用偏移映射L R单点查询公式本身支持无需特判R 超过打表上界索引越界先读所有查询取最大 R 再打表N 1是否可行有争议确认题目对 y 的取值约定N 2应判不可行验证2 % 4 2分支生效大量查询输入输出慢用sys.stdin批量读写这张表是我踩坑后整理的尤其是 L0 和 R 越界这两条实际比赛中真遇到过。养成“先看边界再写主体”的习惯能省很多事。5.3 性能排查为什么我的 Python 超时了超时排查按这个顺序走先看是不是用了input()逐行读换成批量读再看是不是在循环里反复print换成攒列表最后输出然后看打表上界是不是打太大了按实际最大 R 打最后才考虑算法本身是否需要从打表换成公式法。我实测过一个案例同样逻辑逐行input加逐行print的版本跑了三秒多换成批量读写后降到零点几秒。差别全在 I/O不在算法。所以超时先怀疑 I/O别急着推翻思路。注意Python 的整数没有溢出问题这点比 C 省心但也别因此忽略大数运算的性能开销超大范围的前缀和仍然要谨慎。5.4 规律验证的独家小技巧最后分享一个验证规律的小技巧把“可行/不可行”序列打印成一行 0 和 1比如1 0 1 1 1 0 1 1 1 0 ...肉眼扫周期性。平方差可行性的周期是 4序列呈现1 0 1 1的循环。如果打印出来周期不对说明判定条件写错了。这个方法比逐个 assert 更直观尤其适合快速确认“我理解的规律和代码实现是否一致”。我在推导任何带周期性的结论时都会先打印序列看一眼几秒钟的事能避免大量返工。6. 从这道题延伸出去区间统计的通用套路这道题的价值不止于一个答案它示范了一类问题的通用解法性质可 O(1) 判定 区间查询。遇到同类问题套路是固定的——先把判定条件用数学或逻辑化简到最简再决定用打表还是公式。打表适合判定逻辑复杂但范围可控的情况公式适合判定逻辑本身就有闭式表达的情况。这道题两者都行打表更直观公式更省空间选哪个看具体约束。我在其他区间统计题里也反复用这套思路比如统计区间内满足某整除性质的数、满足某数位性质的数。核心永远是两步判定化简、聚合加速。把这两步拆清楚代码结构自然就清晰了。至于 Python 在这里的角色它更像一个思维草稿纸帮你快速把规律跑出来、把边界试出来验证无误后再考虑是否需要用更底层的语言重写。对准备竞赛的人来说这种“先验证后优化”的工作流比一上来就死磕性能要高效得多。