CCPC 华为的一道趣题

本文记录 CCPC 华为比赛中的一道题目。

题面#

骤风起，仓颉飘飘乎不自觉于孤岛焉。岛无人迹，唯有有理数二族尔。一族曰甲分之乙，一族曰乙分之甲，甲、乙皆正整数。数之，则族族不竭其数。

鹦鹉谓仓颉：“日择二数，合其为平均或调和平均。造得一，吾送汝归！”

仓颉能归于九千九百九十九亿九千九百九十九万九千九百九十九日否？

翻译过来就是：仓颉被一阵风刮到了一个荒无人烟的小岛上，岛上有两族有理数 $\frac{a}{b}$ 和 $\frac{b}{a}$（$a$、$b$ 为正整数），每族数都有无穷多个。鹦鹉告诉仓颉：“每天你可以选两个已有的数 $x$、$y$，把它们合成为 $\frac{x+y}{2}$ 或 $\frac{2xy}{x+y}$。如果你能合成出 1，我就送你回家！”问仓颉能否在 999999999999 天内回家。

输入有 $T$ 组数据，每组给出 $a$ 和 $b$。

输入样例：

输出样例：

Yes
No
Yes

做法#

先打表。因为是网络赛，可以先用 Mathematica 求出一些较小的情况，得到 $(1,3)$、$(1,7)$、$(1,15)$、$(7,9)$、$(3,13)$ 等都可以做到。

猜想：约分之后（注意一定要约分），分子分母之和为 2 的幂时可以做到，否则做不到。

写一份代码交上去试一下：

#include <cstdio>
#include <numeric>

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        long long a, b;
        scanf("%lld %lld", &a, &b);
        long long g = std::gcd(a, b);
        long long s = a / g + b / g; // 约分之后分子分母的和
        puts((s & (s - 1)) == 0 ? "Yes" : "No");
    }
}

发现是对的。

证明#

接下来考虑怎么证明。

充分性#

首先，对于 $2^n$ 个数，不断地两两取平均（像归并排序那样一层一层往上合并），经过 $2^n - 1$ 次操作就能得到它们整体的平均值，即

$$\frac{x_1 + x_2 + \cdots + x_{2^n}}{2^n}$$

若既约分数 $\frac{a}{b}$ 满足 $a + b = 2^k$，就可以看作手头有 $2^k$ 个数：$b$ 个 $\frac{a}{b}$ 和 $a$ 个 $\frac{b}{a}$。它们的平均值是

$$\frac{b \cdot \frac{a}{b} + a \cdot \frac{b}{a}}{2^k} = \frac{a + b}{2^k} = 1$$

即可满足条件。

注意，若约分之前分子分母之和就是 2 的幂，那么约分之后也是：公约数 $g$ 整除 $a + b = 2^k$，所以 $g$ 本身也是 2 的幂，$\frac{a+b}{g}$ 仍是 2 的幂。但反过来不成立，约分之前不满足的，约分后也可能满足，例如 $\frac{3}{9}$。因此要先约分，再判断：既约分数的分子分母之和是 2 的幂，就一定可以。

必要性#

那么，对于既约分数，如果分子分母之和不是 2 的幂，会怎么样？

设分数为 $\frac{a}{b}$ 且既约，即 $\gcd(a, b) = 1$。$a + b \ge 2$ 且不是 2 的幂，等价于存在奇素数 $p$ 使得 $p \mid a + b$。

我们证明下面这个性质始终成立：手里的每个数写成既约分数 $\frac{x}{y}$ 之后，都满足 $p \mid x + y$。一开始的 $\frac{a}{b}$ 和 $\frac{b}{a}$ 显然满足。

设手里两个满足条件的既约分数 $\frac{x}{y}$ 和 $\frac{u}{v}$，即 $x \equiv -y$，$u \equiv -v \pmod{p}$。先看算术平均：

$$\frac{1}{2}\left(\frac{x}{y} + \frac{u}{v}\right) = \frac{xv + uy}{2yv}$$

它的分子分母之和满足

$$xv + uy + 2yv \equiv -yv - vy + 2yv = 0 \pmod{p}$$

这一步可能会发生约分，但不会约去 $p$。因为若 $p$ 整除公约数，则 $p \mid 2yv$，而 $p$ 是奇数，所以 $p \mid y$ 或 $p \mid v$。若 $p \mid y$，结合 $p \mid x + y$ 可得 $p \mid x$，与 $\frac{x}{y}$ 是既约分数矛盾；$p \mid v$ 同理。既然公约数不含因子 $p$，约分之后的分子分母之和仍然被 $p$ 整除。

调和平均同理：

$$\frac{2 \cdot \frac{x}{y} \cdot \frac{u}{v}}{\frac{x}{y} + \frac{u}{v}} = \frac{2xu}{xv + uy}, \qquad 2xu + xv + uy \equiv 2yv - yv - vy = 0 \pmod{p}$$

若 $p$ 整除公约数，则 $p \mid 2xu$，即 $p \mid x$ 或 $p \mid u$，同样与既约矛盾。

所以无论怎么合成，得到的数的分子分母之和都含有奇素因子 $p$。而 $1 = \frac{1}{1}$，分子分母之和为 2，不含奇素因子，因此永远得不到 1。

证明完毕。

2026 年 10 月修订。 原文的判定代码重写得更短：改用 std::gcd 和位运算判断 2 的幂，并改用 long long，避免分子分母相加时溢出。必要性部分把第二个分数记作 $\frac{u}{v}$（原文沿用了 $\frac{a}{b}$，容易和题目里的 $a$、$b$ 混淆），并写出了原文一笔带过（“同理”）的调和平均一步。另外，充分性的构造需要 $2^k - 1$ 天；只要 $a + b \le 2^{39}$（$a$、$b$ 在 int 范围内时远远满足），天数限制就不起作用。