企业官网建设流程全解析

1. 这道题到底在问什么

第一次看到“平方差”这三个字配上“打表+前缀和”的标签，我下意识以为是一道纯数学推导题，结果读完题面才发现，它其实是一道披着数论外衣的区间统计题。题目大意是：给定一个区间[L, R]，问这个区间里有多少个整数x可以表示成两个整数的平方差，也就是存在整数a、b使得x = a² - b²。蓝桥杯省赛 A 组把它放在中档位置，很多人卡在“怎么判断一个数能不能写成平方差”这一步，然后就没往下想了。

我先说结论，方便你带着答案去读后面的推导：一个整数x能表示成两个整数平方差，当且仅当x不是形如4k+2的数。换句话说，x mod 4 == 2的数全部不行，其余全部可以。这个结论一旦拿到手，题目就退化成了“统计区间内有多少个数模 4 不等于 2”，而区间可能很大、查询可能很多，于是“打表+前缀和”这套组合拳就顺理成章地登场了。

这篇文章适合两类人看。第一类是正在刷蓝桥杯真题、被这道题卡住或者想看看别人怎么想的同学，我会把从数学推导到代码落地的完整链路拆开讲。第二类是已经会做但想优化、想理解“为什么打表比直接算更稳”的读者，我会重点讲清楚打表策略的选择、前缀和的预处理边界、以及 Python 在这种规模数据下的性能取舍。全文的代码都可以直接跑，参数和边界我都会标清楚，你抄过去改个输入就能用。

需要提前说明的是，题目原始输入格式在不同年份的模拟赛里略有差异，有的是单组L R，有的是多组查询。我下面会以“多组查询、区间可能很大”这个更通用的场景来设计，因为这才是“前缀和”真正发挥价值的地方。如果你遇到的是单组查询，把多组循环去掉即可，核心逻辑完全一致。

2. 从平方差到模 4 判定：结论是怎么推出来的

2.1 先做因式分解，别急着枚举

很多人第一反应是双重循环枚举a和b，看能不能凑出x。这个思路在小范围打表验证时可以用，但作为解题主线是死路，因为a、b的取值范围没有上界，你根本不知道该枚举到多大。正确的入口是代数变形：

x = a² - b² = (a + b)(a - b)

令p = a + b，q = a - b，那么x = p * q。这里有个关键观察：p和q的奇偶性必须一致。因为p + q = 2a是偶数，p - q = 2b也是偶数，所以p和q要么同为奇数，要么同为偶数。这个约束是整道题的题眼，后面所有分类讨论都从这里长出来。

我当初推到这里的时候，习惯性地想“那不就是任意两个同奇偶的因子相乘嘛”，但马上意识到要小心：p和q可以是负数，因为a、b允许取负整数。不过平方差的结果x我们只关心正整数范围（题目区间一般从 1 开始），所以可以只考虑p、q同号且为正的情形，负号的情况对称过去不影响可达性。这一步的严谨性在竞赛里够用了，我提一句是让你心里有数，别在证明题里漏掉。

2.2 分奇偶两类，结论自然浮现

现在按x的奇偶性分情况。

情况一：x是奇数。取p = x，q = 1，两者都是奇数，满足同奇偶。解出a = (p+q)/2 = (x+1)/2，b = (p-q)/2 = (x-1)/2，都是整数。所以所有奇数都能表示。比如x = 9，a = 5，b = 4，25 - 16 = 9，成立。

情况二：x是偶数。此时p、q必须同为偶数（因为同奇偶且乘积为偶数，不可能同为奇数）。设p = 2m，q = 2n，则x = 4mn，也就是说x必须是 4 的倍数。反过来，如果x是 4 的倍数，取m = x/4，n = 1，就能构造出解。所以4 的倍数都能表示，而形如4k+2的偶数不能表示。

把两类合起来：奇数可以，4 的倍数可以，4k+2不行。这就是我在开头给出的结论。你可以拿几个数验证一下：1 = 1²-0²可以，2不行，3 = 2²-1²可以，4 = 2²-0²可以，6不行，7 = 4²-3²可以，8 = 3²-1²可以，10不行。规律非常干净。

提示：这里b允许取 0，所以x = a²这种完全平方数也算“两个整数平方差”，因为b = 0是整数。如果你的题目版本要求a、b都是正整数，那完全平方数要单独排除，读题时务必确认这个细节，我见过有人在这里丢分。

2.3 为什么这个结论值得背下来

从做题效率角度讲，这个模 4 判定是“一次推导、终身受用”的典型。平方差可达性问题在蓝桥杯、各类校赛里反复出现，判定条件几乎不变。你把它记成一句话：模 4 余 2 的数不行，其余都行。以后遇到变体，比如“统计区间内不能表示成平方差的数的个数”，直接统计4k+2的个数即可，连打表都省了。

但要注意，这道题的价值不在于结论本身，而在于它把“数论判定”和“区间统计”两个模块拼在了一起。很多人结论推对了，代码却写挂，问题全出在统计环节。下一节我就讲怎么把判定条件高效地落到区间上。

3. 打表策略：为什么直接算不如先建表

3.1 朴素做法的瓶颈在哪

假设查询是单组[L, R]，最直接的做法是从L遍历到R，对每个数判断x % 4 != 2，计数。单组查询下这个做法完全够用，时间复杂度O(R - L)。但如果R达到10^9甚至更大，或者有多达10^5组查询，逐个遍历就会超时。这就是“打表+前缀和”要解决的问题。

我先把两种方案的复杂度摆出来对比，你一眼就能看出取舍：

这里有个容易被忽略的点：打表的上界N必须覆盖所有查询里出现过的最大R。如果查询的R是动态给出的、事先不知道，你就得先读入所有查询、找到最大上界再建表。这个“先读后建”的顺序是很多人的翻车点，我在第 5 节会专门讲。

3.2 打表到底打的是什么

“打表”这个词听起来玄乎，本质就是把每个位置的结果预先算好存进数组。对这道题，最朴素的想法是开一个布尔数组ok[x]，表示x能否表示成平方差，然后对ok做前缀和。但既然我们已经有了模 4 判定，其实连布尔数组都不用存，直接构造前缀和数组pre[i]表示[1, i]内满足条件的数的个数，递推式是：

pre[i] = pre[i-1] + (1 if i % 4 != 2 else 0)

这样一次O(N)的循环就把表建好了，查询[L, R]时答案是pre[R] - pre[L-1]。注意L-1的边界，当L = 1时pre[0]要定义为 0，这个初始化别漏。

我实测下来，Python 里建一个10^7规模的前缀和数组，用列表推导加itertools.accumulate大概一两秒，内存占用几百 MB，属于可接受范围。如果上界再大，就得考虑用公式直接算，或者用array模块压缩存储。具体选型我在第 4 节展开。

3.3 打表 vs 公式：什么时候该放弃打表

既然模 4 判定这么干净，其实区间内满足条件的数的个数是可以直接算的，不一定非要打表。思路是：[1, n]内模 4 余 2 的数的个数是n // 4（当n % 4 >= 2时再加 1），用n减去它就是答案。这样单次查询O(1)，还省了预处理和内存。

那为什么标题还强调“打表+前缀和”？我的理解是，打表方案更通用、更不容易在边界上出错，尤其适合作为“保底解法”先拿分，再考虑优化。竞赛里时间紧，先把能过的版本写出来，比追求最优解却写挂要划算。而且打表的思路可以迁移到判定条件更复杂的变体题上，公式法一旦条件变了就得重新推。所以我的建议是：先写打表版确保正确，如果数据规模逼着你优化，再换成公式版。两种我都给代码，你自己按需取用。

4. Python 实现：从建表到查询的完整代码

4.1 打表加前缀和的标准写法

先给最稳妥的版本。假设我们已经读入了所有查询，并拿到了最大上界max_r：

import sys from itertools import accumulate def solve(): data = sys.stdin.buffer.read().split() if not data: return t = int(data[0]) queries = [] max_r = 0 idx = 1 for _ in range(t): l = int(data[idx]); r = int(data[idx+1]) idx += 2 queries.append((l, r)) if r > max_r: max_r = r # 建表：pre[i] 表示 [1, i] 内能表示成平方差的数的个数 flags = [0] * (max_r + 1) for i in range(1, max_r + 1): if i % 4 != 2: flags[i] = 1 pre = [0] + list(accumulate(flags[1:])) out = [] for l, r in queries: out.append(str(pre[r] - pre[l-1])) sys.stdout.write("\n".join(out)) if __name__ == "__main__": solve()

这段代码有几个细节值得说。第一，用sys.stdin.buffer.read().split()一次性读入所有输入，比逐行input()快很多，多组查询时差距明显。第二，flags数组我保留了，是为了逻辑清晰；如果你追求极致，可以省掉flags，直接在循环里累加。第三，pre的长度是max_r + 1，pre[0] = 0，这样pre[r] - pre[l-1]在l = 1时也不会越界。

注意：accumulate(flags[1:])这里我做了切片，是因为flags[0]恒为 0，切掉后配合前面的[0]拼接，正好让pre[i]对应[1, i]的和。如果你不切片，pre的下标含义会整体偏移一位，查询时就会错。这种下标偏移是前缀和最常见的 bug 来源，写完一定要拿小数据对拍。

4.2 省内存的写法：不存布尔数组

如果max_r很大，flags和pre两个数组同时存在会吃双倍内存。可以合并成一个循环：

pre = [0] * (max_r + 1) cnt = 0 for i in range(1, max_r + 1): if i % 4 != 2: cnt += 1 pre[i] = cnt

这样只占一个数组。实测max_r = 10^7时，Python 列表存整数大约 80MB 到 300MB 不等（取决于整数对象是否复用），如果内存吃紧，可以改用array('i')：

from array import array pre = array('i', [0]) * (max_r + 1)

array存的是 C 层面的定长整数，内存占用约为列表的几分之一，代价是读写稍慢一点点。我在10^7规模下测过，array版本建表时间多出约 20%，但内存省下一大截，属于值得的交换。

4.3 公式版：不打表也能 O(1) 查询

如果你确认查询规模大到打表不现实，用下面这个函数直接算[1, n]内满足条件的数的个数：

def count_ok(n): if n <= 0: return 0 # [1, n] 内模 4 余 2 的数的个数 bad = n // 4 if n % 4 >= 2: bad += 1 return n - bad

推导过程：每 4 个连续整数里恰好有一个模 4 余 2（即4k+2），所以完整的 4 个一组贡献n // 4个“坏数”；剩下n % 4个余数里，如果余数达到 2，说明还多包含一个4k+2，要再加 1。拿n = 10验证：10 // 4 = 2，10 % 4 = 2 >= 2所以bad = 3（对应 2、6、10），count_ok = 7，和打表结果一致。

查询时ans = count_ok(r) - count_ok(l-1)。这个版本没有预处理、没有内存压力，缺点是依赖你推对了公式。我的习惯是：先用打表版跑通样例，再用公式版对拍，两者结果一致才敢提交公式版。对拍脚本很简单，随机生成几百组[L, R]，两个函数各算一遍比对即可。

5. 实操中踩过的坑与排查清单

5.1 输入顺序导致的建表失败

最常见的翻车场景：题目是多组查询，但代码里先建表再读查询，结果建表时根本不知道max_r是多少。我见过有人直接拍一个10^6的上界硬编码进去，样例过了，但隐藏数据里R超过10^6就数组越界。正确顺序一定是先读完所有查询、求出max_r、再建表。如果题目是流式输入、无法预读，那就只能走公式版，这也是公式版存在的意义之一。

还有一种变体是查询之间相互独立但L、R可能倒置（题目保证L <= R就不用管，没保证就得先交换）。我建议在读入时统一做一次if l > r: l, r = r, l，成本极低，能挡掉一类隐蔽错误。

5.2 前缀和的下标偏移

前面提过，pre[i]的定义必须是“[1, i]的计数”，而不是“[0, i]”。因为 0 能不能表示成平方差这个问题，题目区间通常从 1 开始，把 0 算进去会多计。如果你用pre[i] = pre[i-1] + ok(i)且pre[0] = 0，那么pre[i]天然就是[1, i]的计数，前提是循环从i = 1开始。一旦你从i = 0开始且ok(0)返回真（0 = 0² - 0²确实成立），就会多算一个。这个坑我在早期做题时踩过，样例区间不含 0 所以看不出来，提交就 WA。

排查方法很土但有效：拿L = R = 1测，答案应该是 1；拿L = R = 2测，答案应该是 0；拿L = 1, R = 4测，答案应该是 3（1、3、4）。这三个用例覆盖了奇数、4k+2、4 的倍数三类，能快速定位下标问题。

5.3 常见问题速查表

最后一行那个错误特别典型：有人记成“4 的倍数才行”，把奇数漏了，结果偏小；有人记成“不是 4 的倍数就行”，把4k+2也算进去，结果偏大。判定条件就一句i % 4 != 2，写的时候盯紧这个 2。

提示：如果你用的是 PyPy，array模块的性能优势不明显，反而列表推导加accumulate更快。选型时先看你用的解释器，别盲目套别人的优化。

6. 一点延伸：这类“判定+区间统计”题的通用套路

这道题拆到最后，骨架其实非常通用：先找一个数论或组合上的可达性判定，把问题转化成“区间内满足某条件的数的计数”，再用前缀和把多次查询压到 O(1)。蓝桥杯里同构的题不少，比如“区间内有多少个数是某个表达式的值”“区间内有多少个数的约数个数为奇数”等等，套路一模一样。

我的经验是，遇到这类题先别急着写代码，拿纸把判定条件推干净，最好能写成x % k != c这种形式。一旦判定条件落到模运算上，前缀和几乎是白送的。如果判定条件更复杂、没法用简单模运算表达，那就老老实实打表，把ok数组建出来再做前缀和，思路不变，只是建表那步从公式变成循环。

另外，Python 选手要养成“先读全部输入再处理”的习惯，sys.stdin.buffer.read().split()这套模板建议直接背下来，多组查询场景下能省掉大量 IO 时间。我自己的模板里还会加一个out列表统一输出，避免频繁print拖慢速度，这些细节在数据量大的时候就是过与不过的分界线。

至于这道题本身，我个人在实际操作中的体会是：数学推导花的时间远比写代码多，但推导一旦通了，代码二十分钟就能写完并调对。所以别吝啬在纸上推公式的时间，推清楚了再动手，比边写边试要快得多。