企业官网建设流程全解析

UVa 138 Street Numbers 是我很早就刷到的一道题，第一眼看上去就是“街道门牌号求和”，像是无脑枚举加判断；等你真把前几组值算出来，会发现这些数字跳得极快，暴力枚举很快就追不上了。这道题其实是在考佩尔方程（Pell Equation）的基础应用，也顺便教会你一件事：编程竞赛里很多“数学题”，本质上是让你先观察规律，再用数论工具把 O(n) 的暴力优化成 O(log n) 的递推。

这篇内容适合三类人：第一类是刚接触算法竞赛、想搞懂“为什么别人几毫秒就能跑完”的初学者；第二类是已经会写暴力枚举但总是超时、想找数学优化路径的同学；第三类是纯粹想看一道经典题如何从题面走到标准解法的读者。我会把题目建模、公式推导、佩尔方程递推、完整代码和常见格式坑全部讲透，最后再分享几个我实际踩过的坑。

1. 题目到底在说什么：一个看似简单的街道场景

1.1 题面其实只有一句话

题目描述是这样的：一条街上的房子按 1 到 n 连续编号，你的门牌号是 m。你站在自己家门口往前看，左边所有房子的编号加起来，等于右边所有房子的编号加起来。现在要输出前 10 对满足条件的 (m, n)。

注意，这里“左边”和“右边”都不包括你自己家。举个例子，第一组答案满足 m=6、n=8：左边是 1+2+3+4+5 = 15，右边是 7+8 = 15，正好相等。这里的 m 表示门牌号，n 表示街道最后一栋房子的编号，也就是街道总长度。

很多新手会忽略一个隐含条件：m 必须大于 1，而且 n 必须大于 m。如果 m=1、n=1，左边没有任何房子，右边也没有任何房子，形式上左右和都等于 0，但这显然不是出题人想要的答案。这个边界在后面的佩尔方程解法里会成为非常容易踩的坑，我先在这里标记一下。

1.2 把条件翻译成数学公式

左边所有房子编号之和是：1 + 2 + ... + (m-1) = m(m-1)/2。

右边所有房子编号之和是：(m+1) + (m+2) + ... + n。这个可以看成 1 到 n 的总和减去 1 到 m 的总和，也就是 n(n+1)/2 - m(m+1)/2。

题目要求这两个和相等，所以：

m(m-1)/2 = n(n+1)/2 - m(m+1)/2

两边同时乘以 2，得到：

m(m-1) = n(n+1) - m(m+1)

把括号全部展开：

m² - m = n² + n - m² - m

移项合并，左边和右边的 -m 正好抵消，得到：

2m² = n² + n

这个式子已经非常漂亮了。它说明：对于任意一组答案，门牌号 m 的平方乘以 2，必须恰好等于 n(n+1)。换句话说，这变成一个纯数论问题：寻找正整数 m、n，使得 2m² 等于两个连续整数的乘积。

1.3 一个容易被忽略的隐藏形式

2m² = n² + n 还不是最好用的形式。为了让方程站到标准的数论模型上，我们继续变形。

已知 n² + n = 2m²，两边同时乘以 4，得到 4n² + 4n = 8m²。

给两边都加上 1，左边恰好是完全平方式：

(2n+1)² = 8m² + 1

移项：

(2n+1)² - 8m² = 1

这个形式才是真正的突破口。它长得非常像经典方程 x² - Dy² = 1，也就是佩尔方程的最简形态。只要令 X = 2n+1，Y = 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 组答案列出来，你会立刻感受到这套数据的增长速度：

第一组是 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 换元后的标准形式

上一节我们推导得到了：

(2n+1)² - 8m² = 1

令 X = 2n+1，Y = m，得到：

X² - 8Y² = 1

这就是佩尔方程 x² - Dy² = 1，其中 D = 8。佩尔方程是数论里一个很经典的问题：给定正整数 D，如果它不是完全平方数，那么方程存在无穷多组正整数解，并且所有解都能由一个“最小非平凡解”不断递推生成。

为什么 D 不能是完全平方数？因为如果 D 是完全平方数，x² - y²D 就可以因式分解，解的结构会完全不同。D=8 显然不是完全平方数，所以这个方程有无限多组解，正好对应题目里要求输出前 10 组。

3.2 为什么递推一定能生成所有解

佩尔方程的所有正整数解，都来自环 Z[√D] 里的单位元。对于 D=8，核心观察是：

如果 X₁² - 8Y₁² = 1，X₂² - 8Y₂² = 1，那么它们的“乘积”仍然满足方程。具体来说：

(X₁X₂ + 8Y₁Y₂)² - 8(X₁Y₂ + Y₁X₂)² = (X₁² - 8Y₁²)(X₂² - 8Y₂²) = 1

这个恒等式看起来有点抽象，但它给了我们一个非常实用的结论：只要找到一组最小的正整数解，不断用它去“乘”已有的解，就能依次生成所有解。

对于 D=8，最小非平凡解是 X=3，Y=1，因为 3² - 8×1² = 9 - 8 = 1。于是我们可以定义生成元：

X + Y√8 = (3 + √8)^k

展开之后，相邻两项之间的关系就变成了递推公式。设当前解是 (X, Y)，下一个解是 (X', Y')，那么：

X' = 3X + 8Y
Y' = X + 3Y

这个递推公式的几何含义可以理解为：将当前的解向量在一条双曲线上“旋转”一个固定角度，得到下一组解。每次迭代，解的大小都会扩大大约 3+√8 ≈ 5.83 倍，和前几组答案的增长倍数完全吻合。

3.3 最小解不是要输出的答案

这里有一个特别容易踩的坑。X=3、Y=1 是方程 X² - 8Y² = 1 的最小非平凡解，但它对应的是 n=(3-1)/2=1，m=1。也就是说，它是“m=1, n=1”这个退化情况。

我们在前面已经分析过，m=1 代表自己家左边没有任何房子，这个解虽然满足数学方程，却不是题目要求的合法答案。所以正确做法是从 (X,Y)=(3,1) 出发，先迭代一次，生成第二组解 (X,Y)=(17,6)，这一组对应 n=(17-1)/2=8，m=6，才是真正要输出的第一对答案。

这意味着代码里的循环结构必须小心：不能在进入循环时先把初始 (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 组，或者把 D=8 换成 D=12，你又会陷入暴力枚举的泥潭。

4.3 输出格式：题目没说的那 10 个字符

UVa 138 的另一个考点是输出格式。题目要求每行输出两个数字，每个数字占 10 个字符宽度，右对齐。很多新手在本地看着正常，提交后却提示 Presentation Error，原因就在格式上。

正确写法是：

printf("%10lld%10lld\n", m, n);

这里第一个数字是门牌号 m，第二个数字是街道编号 n，顺序不能反。m 和 n 都是从代码里的变量直接取，m = Y，n = (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 发愣。

根本原因在于，他们没有把“数学上满足方程”和“题目要求合法”区分开。m=1 表示自家左边没有房子，右边从 2 加到 n，除非 n=1，否则右边必然不为 0；而 n=1 时右边也为 0，这是退化解。

解决方案是代码里明确跳过第一组：先迭代，再输出。我把这个逻辑写在循环的开头，就是不让 (3,1) 有机会出现在输出里。

5.3 问题三：int 中途溢出

前 10 组答案看起来不算大，第 10 组的 X = 2n+1 = 131836323，Y = 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)(n+m+1)/2，两者相等即为合法答案。

例如验证第一组 m=6、n=8：

左边 = 6×5/2 = 15
右边 = (8-6)×(8+6+1)/2 = 2×15/2 = 15

两边相等。这个检查方法完全独立于佩尔方程，适合用来验证自己的递推结果。我经常在本地把递推得到的前 10 组数据再用暴力公式检查一遍，确保没有溢出或推导错误。

6. 一些刷题心得

这道题带给我的最大收获，是“先算到第三组，再决定要不要暴力”。很多看起来像是枚举的题目，在枚举前几项之后往往会露出规律。如果你看到相邻答案的比值稳定在一个常数附近，比如这里的 5.8 倍左右，就应该想到佩尔方程或者线性递推。

我个人在做这类题目时还有一个习惯：手动把第一个满足条件的答案验证一遍，然后再把递推公式推到第三项，确保不会有初始项偏移。很多选手栽在“公式推对了，但起始位置差了一步”这种细节上。UVa 138 恰好把这个坑埋得很深，值得记住。

最后再分享一个小技巧：不要只把答案打印出来就结束。你可以顺手在代码里用 check 函数验证每一组合法性，确认无误后再提交。这样即使将来忘记公式，也能用最原始的逻辑兜底。