UVa 138 Street Numbers 是我很早就刷到的一道题第一眼看上去就是“街道门牌号求和”像是无脑枚举加判断等你真把前几组值算出来会发现这些数字跳得极快暴力枚举很快就追不上了。这道题其实是在考佩尔方程Pell Equation的基础应用也顺便教会你一件事编程竞赛里很多“数学题”本质上是让你先观察规律再用数论工具把 O(n) 的暴力优化成 O(log n) 的递推。这篇内容适合三类人第一类是刚接触算法竞赛、想搞懂“为什么别人几毫秒就能跑完”的初学者第二类是已经会写暴力枚举但总是超时、想找数学优化路径的同学第三类是纯粹想看一道经典题如何从题面走到标准解法的读者。我会把题目建模、公式推导、佩尔方程递推、完整代码和常见格式坑全部讲透最后再分享几个我实际踩过的坑。1. 题目到底在说什么一个看似简单的街道场景1.1 题面其实只有一句话题目描述是这样的一条街上的房子按 1 到 n 连续编号你的门牌号是 m。你站在自己家门口往前看左边所有房子的编号加起来等于右边所有房子的编号加起来。现在要输出前 10 对满足条件的 (m, n)。注意这里“左边”和“右边”都不包括你自己家。举个例子第一组答案满足 m6、n8左边是 12345 15右边是 78 15正好相等。这里的 m 表示门牌号n 表示街道最后一栋房子的编号也就是街道总长度。很多新手会忽略一个隐含条件m 必须大于 1而且 n 必须大于 m。如果 m1、n1左边没有任何房子右边也没有任何房子形式上左右和都等于 0但这显然不是出题人想要的答案。这个边界在后面的佩尔方程解法里会成为非常容易踩的坑我先在这里标记一下。1.2 把条件翻译成数学公式左边所有房子编号之和是1 2 ... (m-1) m(m-1)/2。右边所有房子编号之和是(m1) (m2) ... n。这个可以看成 1 到 n 的总和减去 1 到 m 的总和也就是 n(n1)/2 - m(m1)/2。题目要求这两个和相等所以m(m-1)/2 n(n1)/2 - m(m1)/2两边同时乘以 2得到m(m-1) n(n1) - m(m1)把括号全部展开m² - m n² n - m² - m移项合并左边和右边的 -m 正好抵消得到2m² n² n这个式子已经非常漂亮了。它说明对于任意一组答案门牌号 m 的平方乘以 2必须恰好等于 n(n1)。换句话说这变成一个纯数论问题寻找正整数 m、n使得 2m² 等于两个连续整数的乘积。1.3 一个容易被忽略的隐藏形式2m² n² n 还不是最好用的形式。为了让方程站到标准的数论模型上我们继续变形。已知 n² n 2m²两边同时乘以 4得到 4n² 4n 8m²。给两边都加上 1左边恰好是完全平方式(2n1)² 8m² 1移项(2n1)² - 8m² 1这个形式才是真正的突破口。它长得非常像经典方程 x² - Dy² 1也就是佩尔方程的最简形态。只要令 X 2n1Y m原始条件就变成了X² - 8Y² 1到这里一道“门牌号求和”的题目已经被完整地转化成了一个数论问题。整个过程没有用到任何高级技巧只是代数变形但这一步决定了后面算法的上限。2. 暴力的天花板先看看答案增长速度2.1 从最朴素的暴力开始如果还没有接触过佩尔方程绝大多数人第一反应是枚举 m然后检验是否有符合条件的 n。根据等式 2m² n² n我们可以在枚举每个 m 时计算 s 1 8m²如果 s 正好是一个奇数的完全平方数那么 n (√s - 1)/2 就是整数答案。写成 C 大概是下面这个样子#include cstdio #include cmath long long isqrt(long long v) { long long r (long long)sqrt((double)v); while ((r 1) * (r 1) v) r; while (r * r v) --r; return r; } int main() { int cnt 0; for (long long m 2; cnt 10; m) { long long s 1 8 * m * m; long long r isqrt(s); if (r * r s (r 1)) { long long n (r - 1) / 2; if (n m) { printf(%10lld%10lld\n, m, n); cnt; } } } return 0; }其中 isqrt 用整数开方加校正是为了避免浮点 sqrt 的精度误差导致最后几位判断出错。这里的枚举范围看似不大但实际跑起来可能会让你怀疑人生。2.2 前几组答案像是“跳着走”如果把前 10 组答案列出来你会立刻感受到这套数据的增长速度组数mn1682354932042884118916815693098006403915712172354163329288137210519404499799721411309768104661117965918161第一组是 6 和 8第二组直接跳到 35 和 49第三组就是 204 和 288。每过一组数字都变成原来的五六倍。第 10 组的 m 已经超过 4600 万n 接近 6600 万。这说明什么呢暴力枚举前 10 组m 至少要遍历到 4661 万。每次循环都需要做一次乘法、一次开方和若干次校正在本地电脑上可能要跑几十秒在判题环境的严格时限下非常危险。更关键的是如果你哪天想输出前 12 组、前 15 组m 的需求会爆炸式增长暴力法在数学本质上是不可持续的。2.3 为什么暴力不是终点暴力本身不是错误它是验证思路和发现规律的好工具。但当你看到 m 和 n 几乎按固定比例增长时就应该产生一个直觉这背后一定有某种通解递推结构而不是靠一个个枚举去碰运气。第 10 组的 m 已经四千多万如果再算第 11 组大概就是 2.7 亿第 12 组就是十几亿。用枚举去做复杂度跟着答案指数上升而正确答案的数量不会陪你一起指数上升。所以我们必须换到数论思路上来把“寻找”变成“生成”。3. 标准佩尔方程为什么递推能一网打尽3.1 换元后的标准形式上一节我们推导得到了(2n1)² - 8m² 1令 X 2n1Y m得到X² - 8Y² 1这就是佩尔方程 x² - Dy² 1其中 D 8。佩尔方程是数论里一个很经典的问题给定正整数 D如果它不是完全平方数那么方程存在无穷多组正整数解并且所有解都能由一个“最小非平凡解”不断递推生成。为什么 D 不能是完全平方数因为如果 D 是完全平方数x² - y²D 就可以因式分解解的结构会完全不同。D8 显然不是完全平方数所以这个方程有无限多组解正好对应题目里要求输出前 10 组。3.2 为什么递推一定能生成所有解佩尔方程的所有正整数解都来自环 Z[√D] 里的单位元。对于 D8核心观察是如果 X₁² - 8Y₁² 1X₂² - 8Y₂² 1那么它们的“乘积”仍然满足方程。具体来说(X₁X₂ 8Y₁Y₂)² - 8(X₁Y₂ Y₁X₂)² (X₁² - 8Y₁²)(X₂² - 8Y₂²) 1这个恒等式看起来有点抽象但它给了我们一个非常实用的结论只要找到一组最小的正整数解不断用它去“乘”已有的解就能依次生成所有解。对于 D8最小非平凡解是 X3Y1因为 3² - 8×1² 9 - 8 1。于是我们可以定义生成元X Y√8 (3 √8)^k展开之后相邻两项之间的关系就变成了递推公式。设当前解是 (X, Y)下一个解是 (X, Y)那么X 3X 8YY X 3Y这个递推公式的几何含义可以理解为将当前的解向量在一条双曲线上“旋转”一个固定角度得到下一组解。每次迭代解的大小都会扩大大约 3√8 ≈ 5.83 倍和前几组答案的增长倍数完全吻合。3.3 最小解不是要输出的答案这里有一个特别容易踩的坑。X3、Y1 是方程 X² - 8Y² 1 的最小非平凡解但它对应的是 n(3-1)/21m1。也就是说它是“m1, n1”这个退化情况。我们在前面已经分析过m1 代表自己家左边没有任何房子这个解虽然满足数学方程却不是题目要求的合法答案。所以正确做法是从 (X,Y)(3,1) 出发先迭代一次生成第二组解 (X,Y)(17,6)这一组对应 n(17-1)/28m6才是真正要输出的第一对答案。这意味着代码里的循环结构必须小心不能在进入循环时先把初始 (3,1) 当成答案输出否则第一行就会错误地打印 1 1。4. 完整实现与输出格式陷阱4.1 递推版完整 C 代码理解了递推原理之后代码其实非常短。核心就是维护 X 和 Y每次用临时变量保存下一组结果然后输出对应的 m 和 n。#include cstdio int main() { // X 2n 1, Y m // (X, Y) (3, 1) 对应 m 1, n 1不是合法答案所以先迭代再输出 long long X 3, Y 1; int cnt 0; while (cnt 10) { long long nextX 3 * X 8 * Y; long long nextY X 3 * Y; X nextX; Y nextY; long long m Y; long long n (X - 1) / 2; printf(%10lld%10lld\n, m, n); cnt; } return 0; }这组代码在绝大多数评测环境下都是毫秒级完成的。需要注意递推公式必须用 nextX、nextY 两个临时变量不能写成X 3 * X 8 * Y; Y X 3 * Y;因为第二行里的 X 已经是更新后的新值Y 会被算错。这是这类递推题里最高频的低级错误。4.2 打表法为什么也能过但建议别只交表因为这道题的输出内容是固定的 10 行所以很多人会选择直接打表提交代码就是 10 个 printf。这种做法在判题意义上确实能 AC但我非常不建议只学这个。打表能过说明你接受了“答案是固定的”这个事实但如果你希望今后遇到同类佩尔方程问题时能举一反三就必须理解递推来源。打表的结果可以作为验证答案是否正确的手段之一但不能替代解题思路。如果你把前 10 组答案背下来却不明白它们是怎么来的下一次题目改成输出前 20 组或者把 D8 换成 D12你又会陷入暴力枚举的泥潭。4.3 输出格式题目没说的那 10 个字符UVa 138 的另一个考点是输出格式。题目要求每行输出两个数字每个数字占 10 个字符宽度右对齐。很多新手在本地看着正常提交后却提示 Presentation Error原因就在格式上。正确写法是printf(%10lld%10lld\n, m, n);这里第一个数字是门牌号 m第二个数字是街道编号 n顺序不能反。m 和 n 都是从代码里的变量直接取m Yn (X-1)/2。常见的格式错误包括写成printf(%10d %10d\n, ...)在中间多加了一个空格这会导致第二个数字前面变成 11 列与标准输出不一致。使用%-10d左对齐输出会变成左对齐而不是右对齐。行尾多打一个空格。有些判题系统忽略行尾空格有些则不会尽量别冒这个险。调试时打印了额外信息忘了删比如“第 x 组”这样的前缀一定会 WA。我把输出格式单独拿出来讲是因为它实在太容易被忽略了。很多时候你的算法完全正确却因为一个空格丢了 AC这种代价很不值得。5. 常见问题与排查实录5.1 问题一递推更新顺序写错这个问题我在前面已经提过但还是要单独列为一条。使用递推公式时必须先计算新值再统一赋值。错误写法X 3 * X 8 * Y; Y X 3 * Y; // 这里用的 X 已经变了正确做法是用 nextX、nextY 两个临时变量或者先把旧 X 存下来long long oldX X; X 3 * X 8 * Y; Y oldX 3 * Y;这种错误不会导致编译失败但会得到完全错误的数据。如果有输出结果的话前几组就会开始不对排查时需要重点检查递推式两行之间的依赖关系。5.2 问题二初始解选错或把 (3,1) 直接输出还有一类常见错误是从 (X,Y)(3,1) 进入循环后直接打印得到第一行 1 1。我不止一次看到新手把这一组当作答案提交然后对着 WA 发愣。根本原因在于他们没有把“数学上满足方程”和“题目要求合法”区分开。m1 表示自家左边没有房子右边从 2 加到 n除非 n1否则右边必然不为 0而 n1 时右边也为 0这是退化解。解决方案是代码里明确跳过第一组先迭代再输出。我把这个逻辑写在循环的开头就是不让 (3,1) 有机会出现在输出里。5.3 问题三int 中途溢出前 10 组答案看起来不算大第 10 组的 X 2n1 131836323Y 46611179这些数值即使放到 int 里也不会溢出。真正危险的是中间乘法nextX 3 * X 8 * Y在计算第 10 组到第 11 组的过程中3×X 和 8×Y 都会明显超过 21 亿。如果用 int乘法中途就溢出了结果变成负数或截断值。因此统一使用 long long 是更稳妥的选择。如果你把循环扩展成输出前 15 组代码里的 long long 依然安全但扩大到前 30 组时long long 也会逼近极限。不过对于 UVa 138 的要求来说long long 完全够用。5.4 问题四本地验证与提交格式不一致有时候本地运行结果看起来完美一提交就 WA 或 PE。最常见的原因是调试代码没删干净。我的习惯是提交前把主函数里所有和输出答案无关的 printf/cerr 全部注释掉只保留最终输出循环。另一种情况是换行符本地 Windows 下可能用 \r\n提交到 Linux 判题环境时会统一处理通常不是问题。但如果你在输出末尾多打印了一个空行某些判题系统会认为格式错误。5.5 一个小工具用佩尔方程检查任意一组是否为答案如果你自己想验证某对 (m, n) 是否合法除了直接查表还可以用原始条件来计算。左边和是 m(m-1)/2右边和可以用等差公式写成 (n-m)(nm1)/2两者相等即为合法答案。例如验证第一组 m6、n8左边 6×5/2 15右边 (8-6)×(861)/2 2×15/2 15两边相等。这个检查方法完全独立于佩尔方程适合用来验证自己的递推结果。我经常在本地把递推得到的前 10 组数据再用暴力公式检查一遍确保没有溢出或推导错误。6. 一些刷题心得这道题带给我的最大收获是“先算到第三组再决定要不要暴力”。很多看起来像是枚举的题目在枚举前几项之后往往会露出规律。如果你看到相邻答案的比值稳定在一个常数附近比如这里的 5.8 倍左右就应该想到佩尔方程或者线性递推。我个人在做这类题目时还有一个习惯手动把第一个满足条件的答案验证一遍然后再把递推公式推到第三项确保不会有初始项偏移。很多选手栽在“公式推对了但起始位置差了一步”这种细节上。UVa 138 恰好把这个坑埋得很深值得记住。最后再分享一个小技巧不要只把答案打印出来就结束。你可以顺手在代码里用 check 函数验证每一组合法性确认无误后再提交。这样即使将来忘记公式也能用最原始的逻辑兜底。
UVa 138 Street Numbers 是我很早就刷到的一道题第一眼看上去就是“街道门牌号求和”像是无脑枚举加判断等你真把前几组值算出来会发现这些数字跳得极快暴力枚举很快就追不上了。这道题其实是在考佩尔方程Pell Equation的基础应用也顺便教会你一件事编程竞赛里很多“数学题”本质上是让你先观察规律再用数论工具把 O(n) 的暴力优化成 O(log n) 的递推。这篇内容适合三类人第一类是刚接触算法竞赛、想搞懂“为什么别人几毫秒就能跑完”的初学者第二类是已经会写暴力枚举但总是超时、想找数学优化路径的同学第三类是纯粹想看一道经典题如何从题面走到标准解法的读者。我会把题目建模、公式推导、佩尔方程递推、完整代码和常见格式坑全部讲透最后再分享几个我实际踩过的坑。1. 题目到底在说什么一个看似简单的街道场景1.1 题面其实只有一句话题目描述是这样的一条街上的房子按 1 到 n 连续编号你的门牌号是 m。你站在自己家门口往前看左边所有房子的编号加起来等于右边所有房子的编号加起来。现在要输出前 10 对满足条件的 (m, n)。注意这里“左边”和“右边”都不包括你自己家。举个例子第一组答案满足 m6、n8左边是 12345 15右边是 78 15正好相等。这里的 m 表示门牌号n 表示街道最后一栋房子的编号也就是街道总长度。很多新手会忽略一个隐含条件m 必须大于 1而且 n 必须大于 m。如果 m1、n1左边没有任何房子右边也没有任何房子形式上左右和都等于 0但这显然不是出题人想要的答案。这个边界在后面的佩尔方程解法里会成为非常容易踩的坑我先在这里标记一下。1.2 把条件翻译成数学公式左边所有房子编号之和是1 2 ... (m-1) m(m-1)/2。右边所有房子编号之和是(m1) (m2) ... n。这个可以看成 1 到 n 的总和减去 1 到 m 的总和也就是 n(n1)/2 - m(m1)/2。题目要求这两个和相等所以m(m-1)/2 n(n1)/2 - m(m1)/2两边同时乘以 2得到m(m-1) n(n1) - m(m1)把括号全部展开m² - m n² n - m² - m移项合并左边和右边的 -m 正好抵消得到2m² n² n这个式子已经非常漂亮了。它说明对于任意一组答案门牌号 m 的平方乘以 2必须恰好等于 n(n1)。换句话说这变成一个纯数论问题寻找正整数 m、n使得 2m² 等于两个连续整数的乘积。1.3 一个容易被忽略的隐藏形式2m² n² n 还不是最好用的形式。为了让方程站到标准的数论模型上我们继续变形。已知 n² n 2m²两边同时乘以 4得到 4n² 4n 8m²。给两边都加上 1左边恰好是完全平方式(2n1)² 8m² 1移项(2n1)² - 8m² 1这个形式才是真正的突破口。它长得非常像经典方程 x² - Dy² 1也就是佩尔方程的最简形态。只要令 X 2n1Y m原始条件就变成了X² - 8Y² 1到这里一道“门牌号求和”的题目已经被完整地转化成了一个数论问题。整个过程没有用到任何高级技巧只是代数变形但这一步决定了后面算法的上限。2. 暴力的天花板先看看答案增长速度2.1 从最朴素的暴力开始如果还没有接触过佩尔方程绝大多数人第一反应是枚举 m然后检验是否有符合条件的 n。根据等式 2m² n² n我们可以在枚举每个 m 时计算 s 1 8m²如果 s 正好是一个奇数的完全平方数那么 n (√s - 1)/2 就是整数答案。写成 C 大概是下面这个样子#include cstdio #include cmath long long isqrt(long long v) { long long r (long long)sqrt((double)v); while ((r 1) * (r 1) v) r; while (r * r v) --r; return r; } int main() { int cnt 0; for (long long m 2; cnt 10; m) { long long s 1 8 * m * m; long long r isqrt(s); if (r * r s (r 1)) { long long n (r - 1) / 2; if (n m) { printf(%10lld%10lld\n, m, n); cnt; } } } return 0; }其中 isqrt 用整数开方加校正是为了避免浮点 sqrt 的精度误差导致最后几位判断出错。这里的枚举范围看似不大但实际跑起来可能会让你怀疑人生。2.2 前几组答案像是“跳着走”如果把前 10 组答案列出来你会立刻感受到这套数据的增长速度组数mn1682354932042884118916815693098006403915712172354163329288137210519404499799721411309768104661117965918161第一组是 6 和 8第二组直接跳到 35 和 49第三组就是 204 和 288。每过一组数字都变成原来的五六倍。第 10 组的 m 已经超过 4600 万n 接近 6600 万。这说明什么呢暴力枚举前 10 组m 至少要遍历到 4661 万。每次循环都需要做一次乘法、一次开方和若干次校正在本地电脑上可能要跑几十秒在判题环境的严格时限下非常危险。更关键的是如果你哪天想输出前 12 组、前 15 组m 的需求会爆炸式增长暴力法在数学本质上是不可持续的。2.3 为什么暴力不是终点暴力本身不是错误它是验证思路和发现规律的好工具。但当你看到 m 和 n 几乎按固定比例增长时就应该产生一个直觉这背后一定有某种通解递推结构而不是靠一个个枚举去碰运气。第 10 组的 m 已经四千多万如果再算第 11 组大概就是 2.7 亿第 12 组就是十几亿。用枚举去做复杂度跟着答案指数上升而正确答案的数量不会陪你一起指数上升。所以我们必须换到数论思路上来把“寻找”变成“生成”。3. 标准佩尔方程为什么递推能一网打尽3.1 换元后的标准形式上一节我们推导得到了(2n1)² - 8m² 1令 X 2n1Y m得到X² - 8Y² 1这就是佩尔方程 x² - Dy² 1其中 D 8。佩尔方程是数论里一个很经典的问题给定正整数 D如果它不是完全平方数那么方程存在无穷多组正整数解并且所有解都能由一个“最小非平凡解”不断递推生成。为什么 D 不能是完全平方数因为如果 D 是完全平方数x² - y²D 就可以因式分解解的结构会完全不同。D8 显然不是完全平方数所以这个方程有无限多组解正好对应题目里要求输出前 10 组。3.2 为什么递推一定能生成所有解佩尔方程的所有正整数解都来自环 Z[√D] 里的单位元。对于 D8核心观察是如果 X₁² - 8Y₁² 1X₂² - 8Y₂² 1那么它们的“乘积”仍然满足方程。具体来说(X₁X₂ 8Y₁Y₂)² - 8(X₁Y₂ Y₁X₂)² (X₁² - 8Y₁²)(X₂² - 8Y₂²) 1这个恒等式看起来有点抽象但它给了我们一个非常实用的结论只要找到一组最小的正整数解不断用它去“乘”已有的解就能依次生成所有解。对于 D8最小非平凡解是 X3Y1因为 3² - 8×1² 9 - 8 1。于是我们可以定义生成元X Y√8 (3 √8)^k展开之后相邻两项之间的关系就变成了递推公式。设当前解是 (X, Y)下一个解是 (X, Y)那么X 3X 8YY X 3Y这个递推公式的几何含义可以理解为将当前的解向量在一条双曲线上“旋转”一个固定角度得到下一组解。每次迭代解的大小都会扩大大约 3√8 ≈ 5.83 倍和前几组答案的增长倍数完全吻合。3.3 最小解不是要输出的答案这里有一个特别容易踩的坑。X3、Y1 是方程 X² - 8Y² 1 的最小非平凡解但它对应的是 n(3-1)/21m1。也就是说它是“m1, n1”这个退化情况。我们在前面已经分析过m1 代表自己家左边没有任何房子这个解虽然满足数学方程却不是题目要求的合法答案。所以正确做法是从 (X,Y)(3,1) 出发先迭代一次生成第二组解 (X,Y)(17,6)这一组对应 n(17-1)/28m6才是真正要输出的第一对答案。这意味着代码里的循环结构必须小心不能在进入循环时先把初始 (3,1) 当成答案输出否则第一行就会错误地打印 1 1。4. 完整实现与输出格式陷阱4.1 递推版完整 C 代码理解了递推原理之后代码其实非常短。核心就是维护 X 和 Y每次用临时变量保存下一组结果然后输出对应的 m 和 n。#include cstdio int main() { // X 2n 1, Y m // (X, Y) (3, 1) 对应 m 1, n 1不是合法答案所以先迭代再输出 long long X 3, Y 1; int cnt 0; while (cnt 10) { long long nextX 3 * X 8 * Y; long long nextY X 3 * Y; X nextX; Y nextY; long long m Y; long long n (X - 1) / 2; printf(%10lld%10lld\n, m, n); cnt; } return 0; }这组代码在绝大多数评测环境下都是毫秒级完成的。需要注意递推公式必须用 nextX、nextY 两个临时变量不能写成X 3 * X 8 * Y; Y X 3 * Y;因为第二行里的 X 已经是更新后的新值Y 会被算错。这是这类递推题里最高频的低级错误。4.2 打表法为什么也能过但建议别只交表因为这道题的输出内容是固定的 10 行所以很多人会选择直接打表提交代码就是 10 个 printf。这种做法在判题意义上确实能 AC但我非常不建议只学这个。打表能过说明你接受了“答案是固定的”这个事实但如果你希望今后遇到同类佩尔方程问题时能举一反三就必须理解递推来源。打表的结果可以作为验证答案是否正确的手段之一但不能替代解题思路。如果你把前 10 组答案背下来却不明白它们是怎么来的下一次题目改成输出前 20 组或者把 D8 换成 D12你又会陷入暴力枚举的泥潭。4.3 输出格式题目没说的那 10 个字符UVa 138 的另一个考点是输出格式。题目要求每行输出两个数字每个数字占 10 个字符宽度右对齐。很多新手在本地看着正常提交后却提示 Presentation Error原因就在格式上。正确写法是printf(%10lld%10lld\n, m, n);这里第一个数字是门牌号 m第二个数字是街道编号 n顺序不能反。m 和 n 都是从代码里的变量直接取m Yn (X-1)/2。常见的格式错误包括写成printf(%10d %10d\n, ...)在中间多加了一个空格这会导致第二个数字前面变成 11 列与标准输出不一致。使用%-10d左对齐输出会变成左对齐而不是右对齐。行尾多打一个空格。有些判题系统忽略行尾空格有些则不会尽量别冒这个险。调试时打印了额外信息忘了删比如“第 x 组”这样的前缀一定会 WA。我把输出格式单独拿出来讲是因为它实在太容易被忽略了。很多时候你的算法完全正确却因为一个空格丢了 AC这种代价很不值得。5. 常见问题与排查实录5.1 问题一递推更新顺序写错这个问题我在前面已经提过但还是要单独列为一条。使用递推公式时必须先计算新值再统一赋值。错误写法X 3 * X 8 * Y; Y X 3 * Y; // 这里用的 X 已经变了正确做法是用 nextX、nextY 两个临时变量或者先把旧 X 存下来long long oldX X; X 3 * X 8 * Y; Y oldX 3 * Y;这种错误不会导致编译失败但会得到完全错误的数据。如果有输出结果的话前几组就会开始不对排查时需要重点检查递推式两行之间的依赖关系。5.2 问题二初始解选错或把 (3,1) 直接输出还有一类常见错误是从 (X,Y)(3,1) 进入循环后直接打印得到第一行 1 1。我不止一次看到新手把这一组当作答案提交然后对着 WA 发愣。根本原因在于他们没有把“数学上满足方程”和“题目要求合法”区分开。m1 表示自家左边没有房子右边从 2 加到 n除非 n1否则右边必然不为 0而 n1 时右边也为 0这是退化解。解决方案是代码里明确跳过第一组先迭代再输出。我把这个逻辑写在循环的开头就是不让 (3,1) 有机会出现在输出里。5.3 问题三int 中途溢出前 10 组答案看起来不算大第 10 组的 X 2n1 131836323Y 46611179这些数值即使放到 int 里也不会溢出。真正危险的是中间乘法nextX 3 * X 8 * Y在计算第 10 组到第 11 组的过程中3×X 和 8×Y 都会明显超过 21 亿。如果用 int乘法中途就溢出了结果变成负数或截断值。因此统一使用 long long 是更稳妥的选择。如果你把循环扩展成输出前 15 组代码里的 long long 依然安全但扩大到前 30 组时long long 也会逼近极限。不过对于 UVa 138 的要求来说long long 完全够用。5.4 问题四本地验证与提交格式不一致有时候本地运行结果看起来完美一提交就 WA 或 PE。最常见的原因是调试代码没删干净。我的习惯是提交前把主函数里所有和输出答案无关的 printf/cerr 全部注释掉只保留最终输出循环。另一种情况是换行符本地 Windows 下可能用 \r\n提交到 Linux 判题环境时会统一处理通常不是问题。但如果你在输出末尾多打印了一个空行某些判题系统会认为格式错误。5.5 一个小工具用佩尔方程检查任意一组是否为答案如果你自己想验证某对 (m, n) 是否合法除了直接查表还可以用原始条件来计算。左边和是 m(m-1)/2右边和可以用等差公式写成 (n-m)(nm1)/2两者相等即为合法答案。例如验证第一组 m6、n8左边 6×5/2 15右边 (8-6)×(861)/2 2×15/2 15两边相等。这个检查方法完全独立于佩尔方程适合用来验证自己的递推结果。我经常在本地把递推得到的前 10 组数据再用暴力公式检查一遍确保没有溢出或推导错误。6. 一些刷题心得这道题带给我的最大收获是“先算到第三组再决定要不要暴力”。很多看起来像是枚举的题目在枚举前几项之后往往会露出规律。如果你看到相邻答案的比值稳定在一个常数附近比如这里的 5.8 倍左右就应该想到佩尔方程或者线性递推。我个人在做这类题目时还有一个习惯手动把第一个满足条件的答案验证一遍然后再把递推公式推到第三项确保不会有初始项偏移。很多选手栽在“公式推对了但起始位置差了一步”这种细节上。UVa 138 恰好把这个坑埋得很深值得记住。最后再分享一个小技巧不要只把答案打印出来就结束。你可以顺手在代码里用 check 函数验证每一组合法性确认无误后再提交。这样即使将来忘记公式也能用最原始的逻辑兜底。
