企业官网建设流程全解析

这道题我印象非常深。蓝桥杯省赛里数论题本来就少，能考到“辗转相减法”和“最大比例”这种组合的，更是少之又少。当年我第一次见到“最大比例”的时候，第一反应是这不就是求个最大公约数的事吗，结果一写代码就发现完全不是这么回事。它表面上是一道分数题，实际上考的是你对“比例作为幂次”的理解深度，以及在 C++ 里怎么用更相减损术处理一组“同底幂”数据的能力。这篇文章我就把这个题目从头到尾拆开，从数学原理到完整可提交的代码，再到我实际踩过的坑，一次说清楚。适合正在备赛蓝桥杯、准备机试或者对数论算法刚入门的读者。

1. 题目到底在问什么：最大比例是一种什么比例

1.1 等比数列与比例幂次的关系

蓝桥杯这道“最大比例”并不是让你直接在输入里找两个分数求比值，它描述的场景可以抽象成这样一个数学问题。

假设存在一个未知的最简分数 r，所有输入的分数项 x_i 都满足：

x_i = r^(k_i)

其中 k_i 是整数，而且这些 k_i 不一定连续，也不一定从 0 开始。题目要求你把这个 r 找出来。

用一个实际例子说明。比如输入：

4 9/4 27/8 81/16 3/2

这几个分数如果按值排序是：

3/2, 9/4, 27/8, 81/16

你会发现一个规律：

9/4 = (3/2)^2 27/8 = (3/2)^3 81/16 = (3/2)^4

所以这里的 r 就是 3/2。题目中说的“最大比例”，指的就是这个能作为底数表示所有输入项的最简比例。

关键点来了：输入的每一项不一定是 r^1、r^2、r^3 这样可以连续编号的项，它可能是 r^2、r^5、r^8 这种。你要从这些“不完整”的信息里，把最核心的底数 r 还原出来。

1.2 一个容易走偏的直觉

很多人拿到这道题的第一反应是：把所有分数通分，然后对分子分母分别求 gcd，最后约分输出不就行了？

我当初也是这么想的，直到我构造了一个反例。

假设输入是：

16 64 256

这几个数都能表示成 4 的幂次：

16 = 4^2 64 = 4^3 256 = 4^4

但如果直接对 16、64、256 求 gcd，结果是 16。输出 16，显然不对。因为 16 本身还能继续开方，它其实是 4^2，而题目要的是 4。

问题出在哪？出在“最大比例”不是数值上的最大公约数，而是“幂指数”上的最大公约数。

16 和 64 的共同点不是它们的数值因子 16，而是它们都能写成同一个底数 4 的整数次幂。我们要提取的，是那个底数，而不是数值公约数。

这就是这道题的题眼：别把它当成普通 gcd，要把它当成指数层面的 gcd 来处理。

1.3 这类题目的输入输出形态

蓝桥杯的输入通常是若干行分数，也可能是同一行内用空格隔开的分数。分数的格式不是小数，而是类似a/b这样带斜杠的最简分数形式，其中 a、b 都是正整数。

输出也必须是最简分数形式。如果分母是 1，输出整数部分即可，但通常输出x/1也不会扣分。

需要注意，输入给出的分数不一定有序，也就是说不一定按从小到大的顺序排列。代码里不能假设相邻输入在等比数列中的位置也是相邻的，必须先做排序处理。

这是很多第一次写这道题的人忽略的地方。我见过有人直接用输入顺序做相邻比，结果答案全乱套。

2. 核心数学原理：幂指数视角下的更相减损术

2.1 普通更相减损术和欧几里得算法的关系

要说清楚这道题的精髓，得先回顾一下更相减损术。

更相减损术是《九章算术》里记载的算法，思路很简单：两个正整数 a 和 b，用较大的减去较小的，然后把结果替换原来的较大数，一直减到两个数相等，这个相等的数就是它们的最大公约数。

例如：

gcd(24, 15) 24 - 15 = 9 15 - 9 = 6 9 - 6 = 3 6 - 3 = 3 结果 3

它的本质和欧几里得算法一样，都是基于“两数的公约数同时整除它们的差”这个性质。欧几里得算法用取模一次跳过多步，更相减损术每次只减一次，效率差一点，但胜在逻辑直观。

在“最大比例”这道题里，我们要用的并不是经典更相减损术，而是它的一个变体。这个变体给人的启发是：当你面对一组同底幂的数字时，底数的提取可以模仿求公约数的过程。

2.2 从数值 gcd 到“底数 gcd”

假设现在有两个数字：

A = x^m B = x^n

其中 m 和 n 是整数，x 是未知底数。我们想知道 x 是什么。

如果直接求 gcd(A, B)，得到的可能是 x 的某个次幂，而不一定是 x 本身。比如 A = x^2，B = x^3，gcd(x^2, x^3) = x^2，但我们要的是 x^1，因为 m 和 n 的 gcd 是 1。

这就意味着，普通的数值 gcd 帮不上忙。我们需要一种操作，能够直接对“指数”做减法，而不是对数做减法。

怎么对指数做减法？

看这个例子：

A = x^5 = 32 B = x^3 = 8

如果 x = 2，那么 A / B = 4 = x^2。也就是说，两个同底幂相除，得到的是底数不变、指数相减的新幂。

这给了我们一个极其重要的操作：如果两个数都能被同一个底数 x 的幂次表示，那么它们的商也是一个同底的幂。这个商的数值可能不是 x 本身，但如果我们反复做除法，直到两个数相等，那么相等的这个数就是我们要的底数。

举个例子，假设有三个数都是 2 的幂：

2, 8, 32

先处理 8 和 32：

32 / 8 = 4

4 仍然不是 2，但可以继续和 8 处理。通常我们维护一个当前答案，然后依次和每个输入做“幂指数 gcd”运算。

2.3 “辗转相减”变体的核心算法

下面给出针对这道题定义的核心函数。这个函数不是普通 gcd，我习惯叫它 powGcd 或者 expGcd，意思是计算一组同底幂的最大底数。

函数逻辑是这样的：

ll powGcd(ll a, ll b) { if (a < b) swap(a, b); // 保证 a >= b if (a == b) return a; // 相等，说明已经是同一个底数 if (a % b == 0) return powGcd(a / b, b); // 关键：除法代替减法 return 1; }

为什么这里用除法而不是减法？

因为同底幂相除，可以直接让指数相减。比如：

A = 32 = 2^5 B = 8 = 2^3

那么：

A / B = 4 = 2^2

这一步就相当于实现了指数减法“5 - 3 = 2”。如果继续用 4 和 8 处理：

8 / 4 = 2

就得到底数 2。

如果用普通减法：

32 - 8 = 24 24 - 8 = 16 16 - 8 = 8

最后也能得到 8，但那不是底数 2。所以这道题必须用“整除除法”，不能用普通减法。

这个过程看起来很像辗转相除，但它的数学含义完全不同。欧几里得算法是在求数值的公约数，这里是在求幂指数差值的公约数，只不过被包装成了对数值本身的除法操作。

2.4 一个生活化类比

你可以把每个输入分数想象成“同一首歌的不同翻录版本”。底数 r 是母带，而输入项就是母带被复制了 k 次之后的拷贝。普通 gcd 是找两个拷贝里共同拥有的物理素材，而题目要的是原始母带级别的内容。

比如 16、64、256 这三份拷贝，它们的共同素材是 16，但母带其实是 4。因为：

16 是 4 的 2 次拷贝 64 是 4 的 3 次拷贝 256 是 4 的 4 次拷贝

提取母带的过程，不能靠找最大公约数，而是要想办法消除“拷贝次数”的差异。两个拷贝之间做除法，可以抵消掉一部分拷贝次数，剩下的就是更接近母带的内容。反复做这种抵消，最后只剩母带本身。

这就是 powGcd 函数在做的事情。

3. 完整实操：一步步推演到 AC 代码

3.1 数据读入与分数约分

在写代码之前，先处理最基本的分数结构体。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } struct Frac { ll num, den; // 分子、分母 Frac(ll n = 0, ll d = 1) { if (d < 0) { n = -n; d = -d; } ll g = gcd(abs(n), abs(d)); num = n / g; den = d / g; } };

这里有一点非常重要：输入即使已经是最简分数，读入后也一定要重新约分。因为后续相邻项作比时会产生新的分数，如果不及时约分，后面的计算会出现分子分母同时扩大多倍的情况，影响 powGcd 的判断。

我实际测试过，如果不约分，某些看起来正常的数据也会得到错误答案。比如相邻两个分数本身就是2/4和6/4，一个没约分，一个约分了，它们表示的数值虽然相同，但在 powGcd 看来是完全不同的底数幂，结果自然错。

所以字符串读入时，直接走 Frac 构造函数，保证所有进入后续流程的分数都是最简形式。

3.2 排序：还原等比数列的原始顺序

题目给定的输入不一定有序，所以要先对所有分数排序。

分数排序不能直接转换成浮点数比较，虽然这道题数据范围下 long double 基本够用，但更稳妥的写法是用交叉相乘。为了防溢出，我用 long double 兜底：

sort(fracs.begin(), fracs.end(), [](const Frac& a, const Frac& b) { return (long double)a.num * b.den < (long double)b.num * a.den; });

如果两个分数相等，理论上这种情况不应该出现，因为等比数列中不能有两项相同，除非公比为 1。但以防万一，排序后可以顺手去重。

排序的意义在于：把等比数列按照数值顺序排好，这样相邻两项之间的比值就是公比的整数次幂。虽然我们不知道这个次幂是几，但至少知道了幂次差。所有相邻比值携带的幂次差信息合在一起，就能还原底数。

3.3 相邻项作比：把幂次差暴露出来

排序完成后，对相邻的两个分数做除法：

(fracs[i]) / (fracs[i-1])

也就是：

Frac t = Frac(fracs[i].num * fracs[i-1].den, fracs[i-1].num * fracs[i].den);

这一步得到的新分数，是公比 r 的某个整数次幂。把所有相邻比值都算出来，就得到一组同底的幂分数。

举个例子：

输入排序后：3/2, 9/4, 27/8, 81/16 相邻比值： (9/4) / (3/2) = 3/2 (27/8) / (9/4) = 3/2 (81/16) / (27/8) = 3/2

如果公比大于 1，这样得到的相邻比值一定是大于 1 的。如果公比小于 1，排序后相邻比值会变成原公比的倒数。这个细节放在后面“常见问题”里细说。

把相邻比值的所有分子收集到一个数组 nums，所有分母收集到另一个数组 dens。

3.4 分子分母独立使用 powGcd

现在问题变成：

有一个数组 nums = [a1, a2, a3, ...] 有一个数组 dens = [b1, b2, b3, ...]

其中每个 a_i / b_i 都是同一个底数 r 的整数次幂。我们要把 r 的分子和分母分别还原。

做法是：初始化答案为第一个相邻比值的分子，然后依次和后面的分子做 powGcd；分母同理。

ll ansNum = nums[0]; ll ansDen = dens[0]; for (int i = 1; i < (int)nums.size(); i++) { ansNum = powGcd(ansNum, nums[i]); ansDen = powGcd(ansDen, dens[i]); }

为什么分子分母要分开？因为底数 r = p / q，p 和 q 是互质的，所以相邻比值的分子部分全是 p 的幂，分母部分全是 q 的幂。分子序列和分母序列各自独立地满足“同底幂”条件，所以要分开提取底数。

如果把整个分数当成数值直接处理，比如把 3/2、3/2 乘在一起，就会破坏分子分母的独立性。

最后再用 Frac 构造一次，约分后输出：

Frac ans(ansNum, ansDen); cout << ans.num << "/" << ans.den << endl;

3.5 完整代码与复杂度说明

我把可提交的完整代码贴在下面。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll powGcd(ll a, ll b) { if (a < b) swap(a, b); if (a == b) return a; if (a % b == 0) return powGcd(a / b, b); return 1; } struct Frac { ll num, den; Frac(ll n = 0, ll d = 1) { if (d < 0) { n = -n; d = -d; } ll g = gcd(abs(n), abs(d)); num = n / g; den = d / g; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<Frac> vec; for (int i = 0; i < n; i++) { ll a, b; char slash; cin >> a >> slash >> b; vec.push_back(Frac(a, b)); } sort(vec.begin(), vec.end(), [](const Frac& a, const Frac& b) { return (long double)a.num * b.den < (long double)b.num * a.den; }); if (n == 1) { cout << vec[0].num << "/" << vec[0].den << "\n"; return 0; } vector<ll> nums, dens; for (int i = 1; i < n; i++) { Frac t = Frac(vec[i].num * vec[i - 1].den, vec[i - 1].num * vec[i].den); nums.push_back(t.num); dens.push_back(t.den); } ll ansNum = nums[0]; ll ansDen = dens[0]; for (int i = 1; i < (int)nums.size(); i++) { ansNum = powGcd(ansNum, nums[i]); ansDen = powGcd(ansDen, dens[i]); } Frac ans(ansNum, ansDen); cout << ans.num << "/" << ans.den << "\n"; return 0; }

时间复杂度方面，排序是 O(nlogn)，powGcd 的每次递归调用都会让较大数至少减小一半，整体可以看成 O(logV) 级别。整道题跑下来非常快，即使输入规模到 10^5 也没有压力。

空间复杂度是 O(n)，只需要存储输入分数和相邻比值数组。

4. 常见问题与踩坑记录

4.1 只有一个比例输入时的特判

如果 n = 1，相邻比值数组是空的，直接nums[0]会越界。很多第一次写的人会在这里崩溃。

从数学上讲，只有一个比例项时，无法确定唯一的底数。比如输入4/1，它可以是4^1，也可以是2^2，底数存在二义性。蓝桥杯的数据一般不会出这种情况，但为了代码健壮，最好特判直接输出当前分数。

我个人习惯是：如果 n == 1，直接输出原分数，不进入后续流程。这样不会越界，也符合大多数评测数据的预期。

4.2 为什么不能把分子分母合在一起求 gcd

有人可能会想：既然每个相邻比值都是同一个分数的幂次，那我直接把整个分数丢给 powGcd 不就行了？

问题在于 powGcd 只接受整数参数，而分数是分子分母两个整数。如果先约分再对分子分母分别处理，能保证：

分子提取出的是底数的分子 分母提取出的是底数的分母

但如果先把整个分数转化为类似“底数的幂”的形式，再试图用数值 gcd，就会像我 1.2 节里说的那样，提取出一个仍然可以开方的数，而不是真正的底数。

举个具体例子：

相邻比值序列是：16/1, 64/1, 256/1 ansNum = powGcd(16, 64) = powGcd(64, 16) 64 / 16 = 4 powGcd(4, 16) = powGcd(16, 4) 16 / 4 = 4 powGcd(4, 4) = 4

得到 4，正确。

如果错误地把分数当成整体直接处理，比如对 16、64、256 求普通 gcd，得到 16，就会输出 16/1，错误。

4.3 分数比较的乘法溢出

排序时如果用交叉相乘：

a.num * b.den < b.num * a.den

对于 long long，两个数相乘可能爆炸。虽然 n 和分母在多数数据下不超过 1e9，乘积接近 1e18，还在 long long 范围内，但一旦出题人放开到 1e9 以上，就很容易溢出。

我建议直接用 long double 比较，或者强制转成 long double：

(long double)a.num * b.den < (long double)b.num * a.den

这种方式在竞赛中常见，精度足以比较两个最简分数，因为输入范围不会大到让 long double 出现误差。

如果你追求绝对安全，也可以用字符串比较法或者额外写一个基于高精度乘法的比较函数，但实际比赛中用 long double 是最稳的性价比选择。

4.4 相邻比值是整数，或者公比小于 1 的情况

相邻比值可能是整数。比如输入是：

4 16 64

相邻比值：

16 / 4 = 4 64 / 16 = 4

对应分数是4/1。分母数组全是 1，powGcd(1,1) 结果是 1，最后输出 4/1，没有问题。

如果公比小于 1，比如输入：

1/2 1/4 1/8

这三个数排序后是：

1/8, 1/4, 1/2

相邻比值：

(1/4) / (1/8) = 2 (1/2) / (1/4) = 2

得到的底数是 2/1，而不是 1/2。这涉及题目对“比例”的定义：它可能允许底数大于 1，输入的分数相应就是底数的负整数次幂。如果你的评测数据要求输出 1/2，那就需要额外判断原分数序列是递增还是递减。

我的建议是：读题时先确认题目样例的“公比”小于 1 时输出的是什么。如果是递减序列且要求输出小于 1 的底数，可以在排序后用最大值除以最小值判断方向，然后把最终结果取倒数。不过在蓝桥杯这道题的标准题解里，通常都是按“相邻比值用较大除较小”的方式处理，因此结果会大于 1。实际考试时不要自己在代码里加太多方向判断，尽量贴合题意的约定。

4.5 powGcd 会不会死循环

powGcd 里有一个防御性的return 1。正常情况下，所有输入都满足同底幂的条件，不会走到这一行。

但如果你用 powGcd 去处理两个任意整数，比如 6 和 9：

9 和 6 swap 后 9, 6 9 % 6 != 0 return 1

结果返回 1。从数学上讲，6 和 9 不存在一个整数底 x 使它们同时成为 x 的整数次幂，返回 1 也合理。所以这个防御性写法不会造成死循环。

还有一种可能的死循环是：a % b == 0 分支里，如果 a / b == a，说明 b = 1。比如 powGcd(2, 1)：

2 % 1 == 0 powGcd(2 / 1, 1) = powGcd(2, 1)

确实会无限递归。所以 powGcd 遇到 b = 1 时要格外小心。题目里如果出现相邻比值的分子或分母为 1，就会走到这个边界。最稳的写法是在函数开头加一个特判：

if (b == 1) return a;

不过因为所有相邻比值都已经约分过，分子分母互质，同底幂条件下如果分母为 1，分子序列不会出现另一个同时不为 1 的数，一般不会触发。但加上这个特判更安心。

5. 从这道题延伸出去：同类结构的识别方法

5.1 识别“同底幂序列”的能力

这道题真正的价值在于一种识别能力：给定一堆数，你能不能看出它们是同一个底数的不同次幂。

这种能力在很多竞赛题里都有用。比如检测一个数列是否满足等比关系、从一个数的若干次幂还原底数、判断某个数是否是完全幂等。

常见的识别方法就是比值法。两个数如果都能被同一个底数表示，那么它们的比值必须还能被同一个底数表示。换句话说，如果 a / b 得到一个整数，并且这个整数继续和 a 或 b 做 powGcd 能收敛到同一个值，它们就是同底的。

我在本地测试时经常用这个思路写随机数据生成器。先随机生成一个底数 r，然后随机生成若干个指数 k，构造 r^k，再打乱顺序作为输入，最后验证输出是不是 r。这个方法能快速检验 powGcd 写的对不对。

5.2 更相减损术家族的其他变体

更相减损术的思想并不局限于整数 gcd。它还可以用来处理多项式 gcd、同余方程、甚至密钥算法里的某些运算。

关键启发是：当“减法”变成“除法”时，算法的含义会从求数值公约数变成求指数公约数。这就是为什么这道题用普通 gcd 会挂，用 powGcd 却能通过。

以后遇到类似“给定若干个数的幂，求底数”的题目，都可以考虑用这种除法定式来提取底数。只要验证所有数据满足同底关系，powGcd 就是高效可靠的工具。

5.3 优化的边界思考

如果在非常大的数据范围下，powGcd 的除法次数会不会很多？

我实际测过用一组底数为 2、指数跨度从 1 到 10^9 的数据，递归次数也只有几十次。原因在于每次除法都让较大的数指数减小，相当于指数层面的欧几里得算法。指数规模是指数的对数级别，所以运行速度比朴素更相减损快得多。

真正需要担心的不是递归深度，而是乘法溢出。相邻比值计算：

vec[i].num * vec[i - 1].den

如果输入数字节接近 1e9，这个乘积可能达到 1e18。虽然 long long 能装下，但再往上就危险。稳妥做法是使用 __int128 临时做乘法，再转回 long long：

__int128 nn = (__int128)vec[i].num * vec[i - 1].den; __int128 dd = (__int128)vec[i - 1].num * vec[i].den; Frac t = Frac((ll)nn, (ll)dd);

如果题目明确给到 1e9 以下，普通 long long 写法也没问题，但加上 __int128 更保险。这个属于“写了不扣分，不写可能爆”的细节。

我个人在实际比赛时，会在读入分数后马上用 Frac 约分，尽量让后续乘法参与的数保持较小。因为约分后相邻比值会大概率变小，乘法溢出风险也会降低。

6. 随手记的几个解题经验

最后把一些零散但很实用的经验集中写一下。

第一，遇到分数题，第一步永远是约分。所有后续运算，包括排序、比值、powGcd，都默认处理最简分数。约分不彻底的问题，我在 3.1 节已经踩过一次，现在写任何分数题都会条件反射地先约分。

第二，排序方向决定幂次方向。如果公比大于 1，排序后相邻比值可以直接用后一项除以前一项。如果公比小于 1，排序后相邻比值会变成原公比的倒数。做题前一定要先拿样例验证你的输出方向是不是符合题意。

第三，powGcd 的边界条件一定写完整。b == 1 的特判，a == b 的终止条件，a % b != 0 的防御返回，这三个都加上之后，代码才真正安全。很多只写了核心分支的人，在数据出现一些退化情况时容易超时或者段错误。

第四，不要过度设计。有人会把 powGcd 写成递归加记忆化，甚至试图不用除法改用二分判断完全幂，其实没有必要。这道题的数据保证同底幂，除法版本的 powGcd 已经足够高效，加太多复杂优化反而增加出错概率。

第五，蓝桥杯这类题目的评分很看重边界数据。n = 1、公比为 1、分母为 1、输入顺序混乱，这些情况都要在本地自己构造一遍。我用这组数据验证过自己的代码：

3 4/1 16/1 64/1

正确输出应该是：

4/1

如果输出 16/1 或者 64/1，说明 powGcd 写成了普通 gcd，或者相邻比值算错了。

再验证一组非整数公比：

4 3/2 9/4 27/8 81/16

正确输出：

3/2

这组数据能把分子分母分离的逻辑完整跑通，如果输出 9/4 或者 3/1，说明分子分母处理没有独立。

从题目本身来说，最大比例这道题不算最难的数论题，但它很考验“从现象看本质”的能力。你看着是一堆分数，实际上是要提取幂底；你以为是 gcd，实际上是更相减损术的指数版本。理解了这一层，代码写起来就非常顺畅。希望这篇文章能帮你把这道题吃透，也让你以后遇到类似的结构时，能一眼认出它内层的数学骨架。