每台钟都需要一个坏夜晚

城里有一座钟楼。

钟楼的规矩很苛刻：无论哪一天，钟声都必须在一息之内落完。晴天如此，雨天如此，北风穿过齿轮缝隙、把铜针吹得像在犹豫人生的时候，也如此。

可钟楼有个毛病。它不是每天慢。

大多数日子，太阳刚露头，钟声已经响完。几个学徒随机挑日子看，挑来挑去，都是好日子。于是他们开始打磨最大的齿轮。最大的齿轮总在转，浑身油污，特别像罪犯。

打磨了一夜。

钟，快了半根，头发丝。

第二夜，学徒又去打磨弹簧。第三夜，换了润滑油。第四夜，他们规定，齿轮转满三十万次，强行停下。不再拖到天亮。

它干脆不报时了。

后来，守门的老人搬来一排沙漏。他把一年里所有可能让钟楼工作的夜晚写在纸上，一个一个放进去测。最慢的那张纸，钉到墙上。

从那以后，学徒每磨一刀，先看它。

他们仍然不知道下一把锉刀该用在哪里。

但至少，钟，终于有了，一个会反对他们的夜晚。

简化题面

┌─ [P1763] 埃及分数
├─ 平台: 洛谷
├─ 题意: 给定真分数 a/b，把它表示成若干个单位分数 1/x 之和。
├─ 输入: 一对整数 a、b。
├─ 输出: 一组严格递增的分母。先要求项数最少；项数相同时，末项分母尽量大。
├─ 数据范围: 时限 1 秒，内存 128 MiB。
├─ 关键限制: 分母严格递增，且输出须满足两层最优规则。
└─ 完整题面: https://www.luogu.com.cn/problem/P1763

P1763 不会告诉你哪一个分数最难拆。

最开始，我写的是一份很普通的逐层搜索。先试一项，试不到再试两项。每一步选下一个单位分数的分母，减掉它，继续处理剩下的真分数。

这套东西在 3/997 上很快。它给出：

3/997 = 1/345 + 1/14955 + 1/22931

于是 3/997 很容易被误会成一个可靠的朋友。

它不是。

先找那个会让你难堪的分数

不同分数会长出不同形状的搜索树。有些在浅层就找到答案，有些必须证明前几层根本无解；有些分母范围很窄，有些每一层都像给递归又开了一扇门。

如果随手挑一个输入计时，得到的不是程序性能。

运气。

写了一个扫描器。它让程序依次处理：

a = 2..100
b = 200..500

一共 17935 个组合。脚本不说原因，但记下当前最慢者。

原扫描器没有留在仓库。旧记录留下了它启动子进程、计时、刷新最慢输入的行为；下面是按这些可核实行为重建的核心控制流。候选集 cases 就是那 17935 个待测分数，生成时的具体筛选条件已经遗失，不在这里假装记得。

worst_time, worst_case = -1.0, None

for a, b in cases:
    started = time.perf_counter()
    subprocess.run(
        ["tmp.exe"],
        input=f"{a} {b}\n",
        text=True,
        capture_output=True,
        timeout=30,
    )
    elapsed = time.perf_counter() - started

    if elapsed > worst_time:
        worst_time, worst_case = elapsed, (a, b)
        print(f"NEW MAX: {a}/{b}  {elapsed:.3f}s")

它测的是一次完整启动、读入、运行、退出的墙钟时间，不是剥离进程启动开销后的精密微基准。这里不需要那种精度。所有候选都在同一台机器、同一种调用方式下接受同一把尺子；扫描器的任务不是为 gcd 判 0.3% 的生死，而是找出能把搜索树整个摊在桌上的输入。

历史记录是这样爬上去的：

57/229   0.632s
8/241    1.173s
17/421   6.135s
98/499   9.981s

98/499。

一张没有题面特征、没有样例光环的纸。它只是把搜索树拉到了第五层：前四层都得搜完才知道没戏，第五层又要在大量候选之间挑出符合优先级的解。

从这以后，优化才有了基线。

“我觉得这段递归很慢”， NO。

“它在 98/499 上要十秒，而时限是一秒”, YES。

事实(狮史)胜于雄辩(熊遍)。

高明的想法也得跑一次

最后两项都是单位分数时，可以把方程变形，再枚举因子对。 这个想法看起来很体面：少下一层递归，直接用数学收尾。

写完跑扫描器。

3/997 从大约 0.08 秒变成了 5.304 秒。

因子 is not free… 把递归尾部换成枚举因子，从一个地狱换到下一个地狱。对某些分数，后一个地狱待遇还要更差。

这次失败有点丢脸，但得到一个信息。不是“这个思路不够优雅”，不是“也许评测机不同”。它在固定输入上慢了六十多倍。

可以停了。

随后是 gcd。

递归里每走一步都约分，谁看都会觉得它碍眼。两版程序跑同一个坏例，历史记录里的差异约为 3%。目标还差十倍，这 3% 不是突破口。

可以停了。

这里的“停”很重要。优化最危险的地方，不是想不到点子。是已经为一个点子花了两小时以后，它会开始增加你的沉默成本。

固定坏例很有用。

它让一个想法失去继续占用你的权利。

总深度不能替剩余的人花钱

真正有效的一处错误，藏在搜索分母的上界里。

假设还剩 rem 项，当前剩余分数是 a/b。如果下一项分母为 x，剩余每一项最多贡献 1/x，因此必须有：

rem / x >= a / b
x <= rem * b / a

上界里的 rem 是剩余项数。

旧代码却用了总深度 d。

// 错误的历史版本
up = b * d / a;

// 应当使用
up = b * rem / a;

走到第三层时，前两项已经确定。它们不该继续替剩下的搜索扩大预算。总深度为 5、剩余只有 3 项，却按 5 项允许更大的分母范围，每层都多打开一些本来不存在的门。

历史记录里，修这一行后 95/499 从约 5.7 秒降到约 2.1 秒。

一行代码没有因为短而可疑。

它可疑，是因为它改写了搜索空间。它可信，是因为上界推导和同一坏例上的结果指向同一件事。

公式，说明，为什么能剪。

坏例，说明，这次剪到了哪里。

空输出不等于方向错误

后来又尝试了双重迭代：除了逐步增加分解项数，再逐步增加允许的末项分母界。 这个方向第一次跑出来，什么都没有。

空输出很有诱惑力。

它像一句完整的判词：看吧，这个思路不行。

实际的 bug 是，程序找到了一个超过当前界的候选解，也把外层循环标成成功，于是提前退出。

这也是为什么“跑一下”不等于反馈回路。

一份像样的反馈至少分开两件事：

• 它是否比基线快；
• 它是否仍然在解同一道题。

P1763 还有一层麻烦。只检查输出的分数和是否正确，只能证明它分解出了原分数；不能自动证明项数最少，也不能证明末项分母已经按规则最大。 性能计时、合法检查、最优性检查，是三不同的沙漏。

一句“过了测试”，很容易再造一座钟楼。

当前保存的源码是较简洁的 IDDFS 版本，不是历史记录中达到约 0.31 秒的最终组合版本。那份最终源码和原始计时日志没有留存，所以 0.31 秒只能作为当时的记录，不该被今天的文章伪装成复现结果。

这不是遗憾的注脚。

它正好说明了那座钟楼后来还缺一件东西：不仅要有最慢的夜晚，还要留下那一夜的测量方式。

下一次遇到 TLE，先别问“哪一行最慢”。

先问：哪一个输入，能让我在改错时立刻难堪？

找到它以后，程序才开始真正参与讨论。

它不会给建议。

它只会在你自信的时候，响得格外慢。