1. 题目到底在求什么平方和数对的定义1.1 题面描述与输出要求这个标题一看就是刷题日记里的随手记录给定一个整数 N求满足条件的整数对。日期是2024-9-24大概率是某天在题库里遇到的一个数论向简单题。在没有原始题面细节的情况下我按最常见的变体来做讲解给定一个整数 N求出所有满足 a² b² N 的非负整数对 (a, b)并按 a 从小到大输出。这类问题在力扣、蓝桥杯和校招笔试里反复出现过也是许多数学爱好者自己会琢磨的问题。题目条件里最关键的几个词是整数、平方和、有序或无序。很多版本要求 0 ≤ a ≤ b这样才能避免输出 (3,4) 和 (4,3) 这种重复对。而部分版本不限制顺序而是要求“有序对”这时候数量要乘2。如果你的题面来自线上评测系统第一件事就是看输出格式和模棱两可的边界否则再对的算法也会因为漏判重复对而翻车。以 N 25 为例满足条件的整数对有 (0,5) 和 (3,4)一共两组。如果题目允许负数参与情况会立刻变复杂因为平方和只关心绝对值所以 (0,5)、(0,-5)、(3,4)、(3,-4)、(-3,4)、(-3,-4) 等组合都会成为“有序对”输出量可能扩大好几倍。绝大多数编程竞赛题目为了省事都会限定为非负整数对我也建议你把默认解建立在非负整数对上。1.2 这类题目为何经久不衰“给定整数 N 求满足条件的整数对”这个框架下能变形出无数道题从最朴素的 abN到 a×bN到 a²b²N再到 a³b³N每一层变体对应不同的数论技巧。平方和这一版之所以经典是因为它同时考察了枚举上界的推导、浮点误差的规避、重复对的去重三类基本功非常适合作为面试手撕题和算法入门训练题。另一个容易被忽略的点是这道题往往是“高精度运算”的引子。如果你把 N 从 int 变成 64 位整数变成 100 位大整数问题就从“枚举优化”变成了“大整数的加减乘除运算与性能控制”。这也是我在搜索引擎热词里看到“julia高精度浮点数和整数”“大整数加法 并行”“大整数的加减乘除运算”这些词与“整数对”绑定出现在一起的原因——很多人刷完这题之后马上开始思考大数版本。2. 暴力枚举为什么第一个被淘汰2.1 两层循环的天真思路如果没接触过数论优化看到“求整数对”第一反应肯定是双层循环外层 a 从 0 枚举到 N内层 b 从 0 枚举到 N判断 a² b² 是否等于 N。这个写法在 N 很小时完全正确而且代码短到十几行就能跑通。def brute_force(N): result [] for a in range(N 1): for b in range(N 1): if a * a b * b N: result.append((a, b)) return result但如果 N 是 10⁶ 甚至 10⁹这套代码会跑得让人怀疑人生。10⁶ 的双层循环是 10¹² 次迭代每台普通电脑每秒能跑大约 10⁹ 次简单运算10¹² 次意味着几百到几千秒这在任何在线评测系统里都是妥妥的超时。2.2 三个致命伤超时、溢出、重复超时是最容易被意识到的但后面两个坑往往在笔试里更致命。溢出当 N 接近 32 位有符号整数的上限 2,147,483,647 时a 和 b 本身可能达到几万甚至几十万它们的平方瞬间超过 int 范围。你如果用了 int 类型直接计算a * a在 N 较大时会产生未定义行为判断结果永远错误。重复如果不约定 a ≤ b输出结果会包含 (a,b) 和 (b,a) 两份题目如果对结果数量有断言你根本没机会发现多输出了几对因为样例往往恰好是对称性不明显的 N。这里有个很实用的排查技巧先用暴力解跑一批小数据打印出所有结果再拿优化版跑同一批数据逐条比对。我做这类题时一定不会跳过这一步因为优化算法的正确性必须建立在一个可信的基准之上。暴力法也不是一无是处。它能帮你确定题目的输出格式、理解重复对规则还能生成测试用例用于验证后续的优化实现。所以我的建议是先写暴力再写优化用暴力做基准而不是一开始就追求终极解。3. 用数学把搜索空间砍到 O(√N)枚举小根 校验大根3.1 为什么只看一半就够了平方和最大的特点是非负性a² ≥ 0b² ≥ 0。所以如果 a² b² N那么 a² ≤ Nb² ≤ N这意味着 a 和 b 都只能在 [0, √N] 区间内。于是双循环可以从 O(N²) 立刻降到 O((√N)²) O(N)。这看起来已经是质的飞跃但还有更经典的收窄方式——只枚举一个变量通过减法与开方求另一个变量。思路是这样固定 a 从 0 枚举到 √N令 b² N - a²然后判断 N - a² 是否是一个完全平方数。如果是直接得到 b √(N - a²)。这背后的数学依据很简单整数的平方和问题中给定其中一个平方项另一个平方项就被唯一确定了。这个技巧的复杂度是 O(√N)以 N 10⁹ 为例只需要枚举 31623 次现代机器可以说是瞬间完成。对 32 位有符号整数范围内的任意 N这都完全可行。3.2 校验完全平方数的精度处理这里有个新手极易踩进去的坑如何判断一个数是否为完全平方数。最直接的写法是import math def is_perfect_square(x): r int(math.isqrt(x)) return r * r xPython 3.8 之后提供的math.isqrt返回整数平方根没有浮点数误差是我个人强烈推荐的做法。C/C 里没有现成 isqrt常见做法是先int r sqrt(x)然后对 r 和 r1 都检查一下因为浮点开方在边界附近可能少算或多算 1。为什么浮点开方会出错本质是浮点数的存储精度有限。数学上完全平方数在计算机里被求根时得到的结果可能是一个接近整数但差一点点的小数比如sqrt(25)有可能被算成4.999999999999int 截断后变成 4判断就错了。虽然现代硬件上的 libm 实现已经把绝大多数常见输入调到很准但你在竞赛中不能赌这件事尤其是在 N 接近 10¹⁸ 时double 的尾数精度只有大约 15~16 位十进制数字早已不够用。3.3 枚举上界与边界条件枚举 a 的上界应该取math.isqrt(N)而不是int(math.sqrt(N))。注意当 a 恰好等于 √N 时b 必须为 0这一对是否输出取决于题面是否允许 0。大部分题目允许非负整数对因此 (√N, 0) 应该被算入。如果你把上界定到isqrt(N) - 1就会漏掉这个边界对而样例往往不会覆盖这种边角。以 N0 为例a 只能取 0b²0输出 (0,0)。以 N1a0 时 b1a1 时 b0如果约束了 a≤b只输出 (0,1)。以 N2a1b1输出 (1,1)。这些边界值建议在写完代码后全部跑一遍作为自测用例。4. 双指针解法比 sqrt 更稳的实现4.1 单调性与指针移动逻辑如果你不想和浮点数、isqrt 纠缠还有另一种不用开方的漂亮解法——双指针。考虑 a 指向 0b 指向 isqrt(N)然后看 a² b² 与 N 的关系如果 a² b² N记录 (a,b)同时 a 右移、b 左移如果 a² b² N说明平方和太小a 右移增大如果 a² b² N说明平方和太大b 左移减小。这个过程依赖一个单调性事实当 a 固定时b 增大平方和严格增大当 b 固定时a 增大平方和严格增大。所以从两个端点相向而行不会漏解。本质上它是在单调矩阵里搜索等于目标值的位置每次移动一步最多移动 O(√N) 次。def two_pointer(N): result [] a 0 b math.isqrt(N) while a b: s a * a b * b if s N: result.append((a, b)) a 1 b - 1 elif s N: a 1 else: b - 1 return result注意循环条件a b。如果写成a b就会漏掉对角线上的解比如 N2 时的 (1,1)以及 N0 时的 (0,0)。当我第一次写这个算法时就因为循环条件差了一个等于号导致 N2 的输出为空排查了很久才发现。4.2 双指针相比开方法的优势开方法的核心操作是isqrt虽然现在各大语言都有高效实现但如果你手写或者用的语言库里没有就需要自己实现整数二分求根。双指针则只涉及加法和乘法以及整数比较逻辑简单、可控性强不容易引入隐蔽的边界误差。代价是双指针的常数偏大枚举法是每次循环做一次 isqrt而双指针每次循环做一次乘法和加法。两者渐进复杂度一样都只有 O(√N)。实际测试中N 在 32 位范围内两者几乎没有肉眼可见的差别所以选择哪个方案取决于你更信任哪段逻辑。我个人的偏好是刷题时用双指针因为它不需要考虑“是否完全平方数”这个判断逻辑代码更接近“从问题出发的直观推导”写库或者做性能敏感场景时用枚举isqrt因为单次循环更轻。5. 边界条件和“32位有符号整数”的坑5.1 负数、零、平方溢出题目写“给定一个整数 N”没有明确说明 N 的范围时几乎所有 C/C 选手都会默认按 32 位有符号整数处理上限为 2,147,483,647。这个看似安全的假设有两个隐患。第一N 可能为负数。平方和永远不会等于负数所以负数的答案应该是 0 组。有些题目会把 N 限定为正整数但万一没有限定你的代码在一开始就要处理 N 0 的情况。否则枚举上界isqrt(N)在负数输入上会直接报错或产生未定义的事。我的建议是开头加一行if N 0: return []既省时又安全。第二a² b² 中间值可能溢出。双指针算法里虽然 a、b 都不会超过 isqrt(N)但 a*a 这个乘法本身就可能超过 int 上界。以 N 2,147,483,647 为例isqrt(N) ≈ 4634046340² ≈ 2,147,395,600还没超 int但你几乎是在极限边缘跳舞。如果 N 改成 64 位范围int 不管怎么用都会爆。所以只要 N 可能超过 10⁶就老老实实给乘法变量开 long long / int64。5.2 N 大到 64 位甚至大整数怎么办当 N 超出 int64 范围或者你需要处理大整数的平方和问题时算法层面必须切换到大整数运算。C 可以用 Boost.Multiprecision 的 cpp_intPython 直接原生支持任意精度整数Java 用 BigInteger。这时候“求一个整数有多少位”这种操作就派上用场了——用来判断输入规模决定走普通分支还是大数分支。在写大数版本时最大的性能瓶颈反而不是平方计算而是 isqrt 的开方运算。对大整数求整数平方根常用的办法是牛顿迭代法配合x*x n (x1)*(x1)的验证条件。牛顿迭代在整数上收敛很快但要求初值合理如果你图省事也可以用二分法区间上界直接取 1 左移比特数的一半。实测下来对 100 位的整数牛顿迭代通常只需要十几轮就收敛性能完全可用。如果你还想继续压榨性能可以做并行。对大数的乘法和加法用多线程把长整数切成多个等长块分别计算再合并进位这就是“大整数加法 并行”的常见套路。不过这道题核心的枚举逻辑是串行的真正值得并行的是每一轮大数乘法本身。坦白讲竞赛场景下不推荐这么做复杂度陡增收益却有限。5.3 排序输出是常被忽略的细节很多题面要求“按整数对中第一个数升序排列输出”。枚举法天然满足这个要求因为 a 就是从 0 往 √N 递增的。双指针法则不一定——a 从 0 开始向右移但满足条件的 a 并不是每个值恰好一次你需要在收集完所有结果后统一排序或者保证相遇顺序本身符合要求。如果你看到题面里出现“整数排序”这个热词很可能就是在让你注意输出顺序。到这里有个小技巧先收集所有整数对到一个数组最后统一排序并输出不要在收集过程中穿插输出。因为一旦需要去重、合并或排除边界穿插输出会带来一堆重复代码。6. 完整代码与实测用例6.1 C17 实现双指针 防溢出#include bits/stdc.h using namespace std; vectorpairlong long, long long solve(long long N) { vectorpairlong long, long long ans; if (N 0) return ans; long long b sqrt((long double)N); while ((b 1) * (b 1) N) b; while (b * b N) --b; long long a 0; while (a b) { long long left a * a b * b; if (left N) { ans.push_back({a, b}); a; --b; } else if (left N) { a; } else { --b; } } sort(ans.begin(), ans.end()); return ans; }这里对 b 的初始值做了一次浮点 sqrt 修正先取可能的下界再用整数比较往上下各推一步确保 b 是正确的整数平方根。这个“安全检查”比直接信任long long b sqrt(N)稳健得多。6.2 Python 实现枚举 isqrtimport math def solve(N: int) - list: if N 0: return [] ans [] limit math.isqrt(N) for a in range(limit 1): rest N - a * a b math.isqrt(rest) if b * b rest and a b: ans.append((a, b)) return ansPython 有一个独有优势int无上限所以这版代码天然支持大整数。isqrt也是精准整数开方不涉及浮点数。唯一的隐患是列表可能很长当 N 本身能被表示成很多组平方和时结果集会大到影响内存这时候需要考虑流式输出。6.3 测试用例设计我自己实际跑测试时会用这样一组数据N0 → [(0,0)]N1 → [(0,1)]N2 → [(1,1)]N5 → [(1,2)]N13 → [(2,3)]N25 → [(0,5),(3,4)]N3 → []N-7 → []这些用例覆盖了零、对角元素、无解、负数输入四个关键边界。如果你用的是在线评测建议再随机生成一批 N 从 0 到 10000 的用例用暴力法和优化版对拍一旦出现不一致立刻能定位是边界判定还是重复对处理的问题。7. 从这题延伸出的通用套路7.1 “整数对”问题的常见变形“给定一个整数 N 求满足条件的整数对”这个母题换一个条件就换一种解法a b N直接 a ∈ [0,N]bN-aO(N) 枚举a × b N枚举小因子bN/aO(√N)这也是求约数对的经典方法a² b² N本文的主题枚举 开方或双指针a² - b² N化为 (a-b)(ab)N本质是约数对题a³ b³ N没有平方和那么规整往往需要预处理立方表再用两数之和思路。你发现没有这类题目有一个通用的分析框架先分析变量取值的自然上界再利用等式本身把其中一个变量消掉最后用整除、开方、二分等手段做校验。掌握了这个框架绝大多数“整数对”题都不是硬想出来的而是套框架推出来的。7.2 个人刷题体感与建议这道题我前前后后写过多遍每次都能踩到不同的坑。最早是忘了处理 N 为负数第二次是没加去重条件第三次是 C 里中间乘法溢出。老实说这些坑都不难避开但对我这种记性一般的人来说每次重新写一遍反而能加深印象。给后来者一个建议看到“给定整数 N 求整数对”这种标题先不要急着写代码花一分钟在纸上列出几个小 N 的答案。你会发现大部分思路都是自己推出来的而不是靠回忆题解。比如你手算出 N25 的答案是 (0,5)、(3,4)再看双指针跑一遍整个算法的正确性会变得非常直观。另外一个很现实的建议是多准备几种语言的版本。面试时手撕代码常用 Python短小精悍工程落地常写 C/Java需要考虑溢出和性能而当你开始处理超大整数时Python 的无上限整数能帮你快速验证逻辑等验证完毕再改用高精度库实现。平时多练这两种语言面对这类题目就能始终从容。