最大公约数(GCD)与辗转相除法

最大公约数(GCD)与辗转相除法

在面对“求两个大整数 a, b(最高可达 101810^{18})的最大公约数与最小公倍数”时,如果还停留在从 min(a, b) 一路递减枚举的暴力试除法,单次查询 O(min⁡(a,b))O(\min(a, b)) 的耗时足以让程序瞬间 TLE(运行超时);而哪怕背下了短短一行的欧几里得辗转相除法,不少同学依然会在考场上连环踩雷:初赛选择题问“100 以内哪组正整数会让辗转相除执行取模次数最多”,想当然地选了 (100, 99) 结果痛失高分;复赛求最小公倍数时顺手写下 a * b / gcd(a, b),明明最终答案连 100 万都不到,中间的 a * b 却提前撑爆整数上限溢出回绕;更有甚者在 C++11 评测环境下盲目调用 std::gcd 直接喜提 CE(编译错误)!在 GESP 五级认证以及 CSP-J/S 初赛与复赛中,欧几里得恒等式 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b, a \bmod b) 的数论本质、“两步必减半”的 O(log⁡n)O(\log n) 复杂度证明与相邻斐波那契数最坏退化模型、最小公倍数“先除后乘”防溢出铁律,以及裴蜀定理(Bézout’s Identity)的可凑性判据,构成了初等数论模块的绝对基石。本文将从几何直觉与严谨代数两条脉络出发,把这套传承两千三百年的经典算法彻底讲透。

🎯 考纲锚点与核心痛点

📍 对应考点:掌握最大公约数(GCD)与最小公倍数(LCM)的数论定义及素因数分解关系,深入理解欧几里得辗转相除法的正确性原理与 O(log⁡(min⁡(a,b)))O(\log(\min(a, b))) 时间复杂度,熟练编写无溢出的 GCD/LCM 代码并了解裴蜀定理的基本结论。 🎯 适用等级:GESP 五级考点 | CSP-J/S 初赛/复赛必考

在历年 GESP 五级真题与 CSP-J 初复赛中,考生最容易在以下三大痛点上栽跟头:

  1. “只会死背代码,不懂为什么取模后最大公约数丝毫不变”:遇到初赛变式阅读程序题(如交换参数顺序、统计取模次数、分析最坏输入),一旦脱离模板立刻陷入迷茫,误以为最大的相邻数对 (100, 99) 计算最慢;
  2. “求最小公倍数直接写 a * b / gcd(a, b),惨遭中间乘积爆类型”:忽略了计算机算术从左往右求值的顺序——哪怕最终的 lcm(a, b) 完全装得下,先算 a * b 也会把数值凭空放大 gcd(a, b) 倍,瞬间击穿 32 位甚至 64 位整数边界;
  3. “依赖非标准库函数或写错递归出口,埋下 CE 与除零 RE 隐患”:考场混用 C++17 才引入的 std::gcd 与 GCC 编译器私货 __gcd,或把递归基准条件错写成 if (a % b == 0),一旦题中出现 0 直接触发除以零运行崩溃(Floating Point Exception)。

🧠 一、 核心原理深度拆解(有理论)

1. 为什么 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b, a \bmod b)?几何铺砖与整除双夹证明

设 a, b 为正整数,带余除法将 a 表示为 a=k⋅b+ra = k \cdot b + r(其中商 k=⌊a/b⌋k = \lfloor a / b \rfloor,余数 r=a mod br = a \bmod b,满足 0≤r<b0 \le r < b)。为什么一对大数 (a, b) 的最大公约数,会与缩小后的 (b, r) 完全相等?

我们可以用最直观的长方形正方形铺砖模型一眼看穿它的几何本质:求 gcd(a, b),等价于寻找能严丝合缝铺满长 a、宽 b 矩形而无需裁剪的最大正方形地砖边长 d。

================================================================================
【欧几里得辗转相除法的“正方形铺砖”几何直观图(以 a = 48, b = 18 为例)】

  |<-------------------- a = 48 -------------------->|
  +----------------+----------------+----------+-----+  ───
  |                |                |  12×12   | 6×6 |   ▲
  |     18 × 18    |     18 × 18    |          +-----+   │ b = 18
  |    大正方形    |    大正方形    |          | 6×6 |   ▼
  +----------------+----------------+----------+-----+  ───
  |<--- b = 18 --->|<--- b = 18 --->|<--- r = 12 --->|

  ▶ 第 1 轮裁切:48 = 2 × 18 + 12。任何能铺满 18×18 的地砖,必然也能铺满左边的
                 两个 18×18 区域;因此问题瞬间等价于铺满右侧剩余的【18 × 12】矩形!
  ▶ 第 2 轮裁切:18 = 1 × 12 + 6,问题继续缩小为铺满右下角【12 × 6】矩形!
  ▶ 第 3 轮裁切:12 = 2 × 6 + 0,恰好被两个【6 × 6】正方形铺满无剩余!
                 故最大正方形边长 gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6!
================================================================================

从代数整除角度,只需两行即可完成双向充要证明(证 (a, b) 与 (b, r) 的全体公因数集合完全相同):

  • 正向推导:设任意整数 d 同时整除 a 和 b(即 d∣ad \mid a 且 d∣bd \mid b)。由于 r=a−k⋅br = a - k \cdot b,整除具有线性组合保持性,故 d 必然也能整除 r(即 d∣bd \mid b 且 d∣rd \mid r);
  • 反向推导:反之,若 d∣bd \mid b 且 d∣rd \mid r,则 d 必然也能整除 k⋅b+r=ak \cdot b + r = a(即 d∣ad \mid a 且 d∣bd \mid b)。

既然数对 (a, b) 与数对 (b, a % b) 拥有一模一样的公因数集合,它们的最大公约数自然绝对相等!当辗转相除一路推进到余数为 0,变成 gcd(d, 0) 时(注意任何非零整数都能整除 0,因为 0 = 0 * d),最大公约数就是此时的非零数 d。


2. 为什么快如闪电?“两步必减半”定理与斐波那契最坏情况

许多初学者好奇:取模运算 r = a % b 会不会每次只减小一点点(比如从 100 变成 99、98……),从而退化成 O(n)O(n)?答案是:绝对不可能!

(1)严格 O(log⁡(min⁡(a,b)))O(\log(\min(a, b))) 证明:每 2 步至少折半

考察连续两步状态转移 (a, b) -> (b, r) -> (r, b % r)(不妨设 a≥b>0a \ge b > 0,则 r=a mod br = a \bmod b):

  • 情况 A(b≤a/2b \le a / 2):由于余数严格小于除数,必有 r<b≤a2r < b \le \frac{a}{2};
  • 情况 B(b>a/2b > a / 2):此时 a 里最多只装得下 1 个 b(即商 k = 1),因此余数就是两者之差 r=a−b<a−a2=a2r = a - b < a - \frac{a}{2} = \frac{a}{2}!

无论是情况 A 还是情况 B,都有 a mod b<a2a \bmod b < \frac{a}{2} 恒成立!这意味着在辗转相除序列中,每经过 2 次取模运算,参数规模至少缩小为原来的二分之一。即便面对高达 101810^{18}(约 2602^{60})的 long long 极限大数,总取模步数也绝不会超过 2 * 60 = 120 次,时间复杂度严格为 O(log⁡(min⁡(a,b)))O(\log(\min(a, b)))!

(2)初赛王牌考点:什么时候步数最多?(拉梅定理与斐波那契数列)

怎样让数字缩小得最慢,把辗转相除“卡”到最大步数?显然要让每一步的商 k 都尽可能小——即每一步商都恰好等于 1! 从终点 (1, 0) 令商全为 1 逆向倒推(ri−1=ri+ri+1r_{i-1} = r_i + r_{i+1}),得到的序列依次是:

(1, 0) <- (1, 1) <- (2, 1) <- (3, 2) <- (5, 3) <- (8, 5) <- (13, 8) <- (21, 13) <- (34, 21) <- (55, 34) <- (89, 55) ...

这正是大名鼎鼎的相邻斐波那契数(Fibonacci Numbers)!法国数学家拉梅(Gabriel Lamé)证明了:在 a >= b > 0 前提下,若欧几里得算法需要执行 k 次取模,则最小的输入正整数对恰为相邻斐波那契数 (Fk+2,Fk+1)(F_{k+2}, F_{k+1})。相反,看似吓人的相邻大数 (100, 99) 第 1 步 100 % 99 = 1,第 2 步 99 % 1 = 0,仅仅 2 步就瞬间秒杀!


3. 最小公倍数(LCM)防溢出铁律与裴蜀定理导引

(1)GCD 与 LCM 的对偶恒等式及“先除后乘”铁律

从唯一分解定理来看,设 a=∏piαia = \prod p_i^{\alpha_i},b=∏piβib = \prod p_i^{\beta_i},则:

gcd⁡(a,b)=∏pimin⁡(αi,βi),lcm⁡(a,b)=∏pimax⁡(αi,βi)\gcd(a, b) = \prod p_i^{\min(\alpha_i, \beta_i)}, \qquad \operatorname{lcm}(a, b) = \prod p_i^{\max(\alpha_i, \beta_i)}

由于对任意两个实数恒有 min⁡(α,β)+max⁡(α,β)=α+β\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta,两式相乘立即导出黄金恒等式:

a×b=gcd⁡(a,b)×lcm⁡(a,b)a \times b = \gcd(a, b) \times \operatorname{lcm}(a, b)

但在写 C++ 代码求解 lcm(a, b) 时,下面两种写法有着满分与零分的天壤之别:

写法对比代码表达式算术求值轨迹(设 32 位无符号整数 a=80000, b=90000)最终结果与安全性
高危错误写法a * b / gcd(a, b)先算 80000 * 90000 = 7.2e9(超 232−12^{32}-1 溢出回绕为 2905032704),再除以 10000290503(严重溢出 ❌)
满分标准写法a / gcd(a, b) * b因为 gcd(a, b) 必然整除 a,先精确整除得 8,再乘 90000(推荐左乘 1LL *)720000(零冗余膨胀 ✅)

(2)裴蜀定理(Bézout’s Identity)核心结论

既然辗转相除每一步的余数都是前两项的整数线性组合,一路回代到开头就能证明数论名定理——裴蜀定理:

对于任意不全为 0 的整数 a, b,关于未知整数 x, y 的二元一次不定方程 ax+by=ca x + b y = c 有整数解的充要条件是 gcd⁡(a,b)∣c\gcd(a, b) \mid c(即 c 必须是 gcd(a, b) 的整数倍)。特别地,ax + by 所能凑出的最小正整数恰好等于 gcd⁡(a,b)\gcd(a, b);当且仅当 a, b 互质(gcd⁡(a,b)=1\gcd(a, b) = 1)时,存在整数 x, y 使得 ax+by=1a x + b y = 1。

例如:给你一个容量 6 升和一个容量 9 升的无刻度水壶(水无限供应),能否倒出恰好 4 升水?因为每次装满、倒空、互倒都只是在做 6x + 9y 的整数加减组合,而 gcd(6, 9) = 3,3 不能整除 4,由裴蜀定理一秒判定:永远不可能凑出 4 升!

💡 考场黄金法则(背诵直接套用):

  1. 【三行手写欧几里得,出口认准 b == 0】:严格 C++11 考场环境下绝不依赖 std::gcd 或 __gcd,统一手写 long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }——不仅天然兼容 b == 0 边界,而且当 a < b 时第 1 步 a % b = a 会自动完成两数交换,无需画蛇添足写 swap!
  2. 【求 LCM 必先除后乘,防爆套上 1LL】:凡是计算最小公倍数,肌肉记忆锁定 1LL * (a / gcd(a, b)) * b——先用 gcd 把 a 缩小再乘 b,彻底消灭中间乘积的无谓溢出!

🔍 二、 具象代码与数据推演(有举例)

示例:a < b 自动交换机制推演与 LCM 溢出对比实验

下面这段 24 行的标准 C++11 程序,先追踪当传入第一个参数小于第二个参数(a = 18, b = 48)时辗转相除每一轮的变量演变,随后演示 a = 80000, b = 90000 在 32 位无符号整数下“先乘后除”与“先除后乘”的真实输出差异:

#include <iostream>
using namespace std;

int trace_gcd(int a, int b) {
    int step = 0;
    while (b != 0) {
        int r = a % b;
        step++;
        cout << "Step " << step << ": a=" << a << ", b=" << b << " -> r=" << r << endl;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int g = trace_gcd(18, 48);
    cout << "gcd(18, 48) = " << g << endl;

    unsigned int u = 80000, v = 90000, d = 10000; // 真实 gcd=10000, 真实 lcm=720000
    unsigned int bad_lcm = (u * v) / d;           // 陷阱:80000*90000=7.2e9 提前溢出 32 位上限
    unsigned int ok_lcm  = (u / d) * v;           // 正确:先整除得 8,再乘 90000 = 720000
    cout << "bad_lcm=" << bad_lcm << ", ok_lcm=" << ok_lcm << endl;
    return 0;
}

分步内存变量变化与辗转推演表

执行阶段循环前 a循环前 b余数 r = a % b循环后新 (a, b)核心机制剖析
Step 1184818 % 48 = 18(48, 18)a < b 时余数等于 a,耗费 1 步自动翻转成大数在前!
Step 2481848 % 18 = 12(18, 12)48 = 2 * 18 + 12,规模大幅缩减
Step 3181218 % 12 = 6(12, 6)18 = 1 * 12 + 6(相比 Step 2 的 48 已不足一半)
Step 412612 % 6 = 0(6, 0)余数归零,下一轮 b != 0 为假,退出循环返回 6
LCM 对比u = 80000v = 90000u * v 达 7.2e9bad = 290503明明真实答案 720000 远小于 2322^{32},先乘却白白溢出报错!

程序标准输出:

Step 1: a=18, b=48 -> r=18
Step 2: a=48, b=18 -> r=12
Step 3: a=18, b=12 -> r=6
Step 4: a=12, b=6 -> r=0
gcd(18, 48) = 6
bad_lcm=290503, ok_lcm=720000

⚡ 三、 考场高频避坑指南(正误辨析)

在 GESP 五级判断题与 CSP-J 考场上,以下三个高频雷区是命题人最偏爱的设陷角度:

❌ 易错点 1:把递归终止条件写成 if (a % b == 0) return b;,遇到 0 瞬间除零崩溃!

  • 错误代码:int gcd(int a, int b) { if (a % b == 0) return b; return gcd(b, a % b); }。
  • 为什么错:当题目输入可能包含坐标原点或差值为 0(例如网格斜率向量化简 (dx, dy) = (5, 0))时,一旦调用 gcd(5, 0),第一句 a % b 就会立刻执行 5 % 0,在底层硬件触发 SIGFPE(除以零浮点异常,直接判 RE 0 分)!相反,标准写法 if (b == 0) return a; 先拦截了 b == 0 的情况,根本不会触碰 % 0 红线,安全返回 gcd(5, 0) = 5!
  • 正确规范:永远以 b == 0 作为唯一基准出口;若参数可能为负数(如坐标差 dx < 0),传入前先取绝对值 gcd(abs(dx), abs(dy)),确保返回的公约数恒为非负数。

❌ 易错点 2:把两数乘积恒等式盲目推广到三个数,误以为 gcd⁡(a,b,c)×lcm⁡(a,b,c)=a⋅b⋅c\gcd(a,b,c) \times \operatorname{lcm}(a,b,c) = a \cdot b \cdot c!

  • 错误认知:既然两个正整数恒有 gcd⁡(a,b)×lcm⁡(a,b)=a×b\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b,那么求三个正整数的最小公倍数直接算 a * b * c / gcd(gcd(a, b), c) 就行了!
  • 为什么错:对于三个指数 α,β,γ\alpha, \beta, \gamma,min⁡(α,β,γ)+max⁡(α,β,γ)\min(\alpha, \beta, \gamma) + \max(\alpha, \beta, \gamma) 并不等于 α+β+γ\alpha + \beta + \gamma(中间那个大小居中的指数被漏掉了)!举一个最简单的反例:取 a = 2, b = 2, c = 2,显然 gcd(2, 2, 2) = 2 且 lcm(2, 2, 2) = 2,左边乘积为 2 * 2 = 4,而右边 a * b * c = 2 * 2 * 2 = 8,两者根本不相等!
  • 正确规范:求多个数的 GCD 或 LCM,必须采用两两递推迭代法:
    • 多元 GCD:g = gcd(gcd(a, b), c);
    • 多元 LCM:先算前两数的最小公倍数 L12 = a / gcd(a, b) * b,再拿 L12 与第三个数按两数公式求公倍数 L123 = L12 / gcd(L12, c) * c!

❌ 易错点 3:在 C++11/14 赛场环境盲目调用 std::gcd 或轻信 GCC 私货 __gcd!

  • 错误操作:不背手写模板,考场直接 #include <numeric> 调 gcd(a, b),或者 #include <algorithm> 调 __gcd(a, b)。
  • 为什么错:
    1. 标准库的 std::gcd 与 std::lcm 直到 C++17 标准才正式加入!在限定 -std=c++11 或老版本编译参数的评测机上会直接报编译错误(CE);
    2. 双下划线开头的 __gcd(x, y) 属于 GCC 编译器的内部私有扩展函数:一方面它要求两个模板参数类型必须严格一致,写 __gcd(12, 18LL)(int 与 long long 混传)会直接模板推导失败 CE;另一方面传入负数时会算出负的“最大公约数”,极易破坏分数化简符号!
  • 正确规范:3 行手写欧几里得函数耗时不到 15 秒,兼容一切 C++ 标准且行为完全可控,考场上一律手写!

📝 四、 真题实战演练与精析(有例题:3 道)

【例题 1 · 单选题】(CSP-J 初赛阅读程序经典题:辗转相除取模次数极值分析)

题目:阅读以下 C++11 函数定义:

int gcd_steps(int a, int b) {
    if (b == 0) return 0;
    return 1 + gcd_steps(b, a % b);
}

若限制输入的两个实参 a, b 均为 [1, 100] 范围内的正整数,在下列四组参数调用中,哪一组使得 gcd_steps(a, b) 的返回值最大(即执行 % 取模运算的次数最多)?( )

  • A. gcd_steps(100, 99)
  • B. gcd_steps(96, 64)
  • C. gcd_steps(89, 55)
  • D. gcd_steps(55, 89)

🔍 答案与逐项排除解析:

  • 正确答案:D
  • 解析过程:
    1. 排除 A:最具迷惑性的直觉陷阱!100 和 99 虽然数值最大且互质,但第 1 步 100 % 99 = 1,第 2 步 99 % 1 = 0,随后到达 b == 0 出口,总计仅返回 2;
    2. 排除 B:96 % 64 = 32,64 % 32 = 0,同样只需 2 次取模;
    3. 对比 C 与 D(斐波那契最坏情况 + 参数翻转加步):注意到 100 以内的斐波那契数列依次为 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89。
      • 对于 C 项 (89, 55):由于 89 > 55,每一步商均为 1,依次经历 (89,55) -> (55,34) -> (34,21) -> (21,13) -> (13,8) -> (8,5) -> (5,3) -> (3,2) -> (2,1) -> (1,0),共执行 9 次取模;
      • 对于 D 项 (55, 89):由于传入时满足 55 < 89,第 1 次调用执行 55 % 89 = 55 将状态翻转为 gcd_steps(89, 55),白白多花 1 次取模,随后再走完 (89, 55) 的 9 次取模,合计达到 1 + 9 = 10 次(这也是整个 [1, 100] x [1, 100] 区间内的全局最大值)!故锁定 D。

【例题 2 · 判断题】(GESP 五级数论与类型边界辨析:“先除后乘”能否保住 int 不溢出?)

题目:在 C++11 标准(int 为 32 位有符号整数,上限为 231−1≈2.14×1092^{31} - 1 \approx 2.14 \times 10^9)下,已知两个 int 型正整数变量 a, b 满足 1≤a,b≤1091 \le a, b \le 10^9。为了求它们的最小公倍数,只要严格遵守“先除后乘”原则编写语句 int ans = a / gcd(a, b) * b;,就一定不会发生 int 算术溢出。( )

🔍 答案与反例证明:

  • 结论:错误(×)
  • 辨析证明:
    1. 厘清“消除中间冗余膨胀”与“最终结果本身超限”的区别:“先除后乘”的作用是保证计算中途的数值绝不会超过最终答案 lcm(a, b) 本身(避免出现最终答案小于 2e9 但 a * b 提前溢出的冤案);但它无法改变 lcm(a, b) 本身的数学大小!
    2. 极简反例:取两个互质的 int 正整数 a = 100000(10510^5),b = 99999。显然 a, b 均远小于 10910^9,且相邻正整数必互质,即 gcd(a, b) = 1。此时执行 a / gcd(a, b) * b:先除得 100000 / 1 = 100000,再乘 99999,真实最小公倍数高达 9.9999×1099.9999 \times 10^9,远超 32 位 int 上限 2.14×1092.14 \times 10^9,照样在 * b 这一步发生有符号整数溢出!
    3. 正确准则:当 a, b 可达 10910^9 时,其最小公倍数最大可达 101810^{18} 量级,不仅要先除后乘,还必须将返回值和乘数提升至 64 位 long long(即 long long ans = 1LL * (a / gcd(a, b)) * b;)!

【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛常考母题:有理分数序列的防溢出通分求和与最简化简)

题目描述:给定 n(1≤n≤201 \le n \le 20)个有理分数 aibi\frac{a_i}{b_i}(其中分子 −109≤ai≤109-10^9 \le a_i \le 10^9,分母 1≤bi≤1091 \le b_i \le 10^9)。请精确计算这 n 个分数的累加总和 ∑i=1naibi\sum_{i=1}^{n} \frac{a_i}{b_i},并将最终结果化简为最简分数形式 P/Q 输出(要求分母 Q > 0 且 gcd⁡(∣P∣,Q)=1\gcd(|P|, Q) = 1;特别地,若累加和恰好为 0,则标准最简形式规定输出为 0/1)。题目保证任意前缀累加和经约分后的最简分子绝对值与最简分母均不超过 101210^{12}。

输入格式: 第一行包含一个正整数 n,表示待累加的分数个数。 接下来 n 行,每行包含两个整数 a_i, b_i,表示第 i 个分数的分子与分母。

输出格式: 输出一行,格式为 P/Q,表示化简后的最简分数总和。

💡 算法建模与防溢出核心要点:

  1. 读入即约分:题目输入的单个分数如 200000000 / 600000000 可能带有高达 2×1082 \times 10^8 的冗余公因数,先用 gcd(|a|, b) 约成 1 / 3 可大幅降低分母量级;
  2. LCM 通分防爆:合并当前最简累加和 num / den 与新分数 a / b 时,绝不能直接硬乘分母 den * b(最高可达 102110^{21} 撑爆 long long),而应先求 g1 = gcd(den, b),用先除后乘算出最小公分母 L = (den / g1) * b,分子对应交叉乘以互质商 num * (b / g1) + a * (den / g1);
  3. 零值自动归一魔法:每次相加后立即求 g2 = gcd(|next_num|, L) 并同除 g2。当分子恰好正负抵消变成 0 时,由于标准欧几里得函数满足 gcd(0, L) == L,执行 0 / L = 0 与 L / L = 1 会天然把 0/L 完美规整为 0/1,连特判 if 都省了!
#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long my_abs(long long x) {
    return x < 0 ? -x : x;
}

int main() {
    int n;
    cin >> n;

    // 初始累加和表示为最简有理分数 0/1
    long long num = 0, den = 1;

    for (int i = 1; i <= n; i++) {
        long long a, b;
        cin >> a >> b;

        // 1. 先将当前读入的分数自身化为最简,提前消除冗余大公因数
        long long g0 = gcd(my_abs(a), b);
        a /= g0;
        b /= g0;

        // 2. 求两分母的最小公倍数作为公分母:严格遵循“先除后乘”防溢出铁律
        long long g1 = gcd(den, b);
        long long common_den = (den / g1) * b;
        long long next_num = num * (b / g1) + a * (den / g1);

        // 3. 累加结果再次立即约分;当 next_num 为 0 时 gcd(0, common_den) == common_den,自动归为 0/1
        long long g2 = gcd(my_abs(next_num), common_den);
        num = next_num / g2;
        den = common_den / g2;
    }

    cout << num << "/" << den << endl;
    return 0;
}
  • 输入样例:
    4
    200000000 600000000
    1 6
    -500000000 1000000000
    3 8
  • 输出样例:
    3/8
    (样例解释:第 1 个分数先约分为 1/3;加上第 2 个分数 1/6 时,公分母为 lcm(3, 6) = 6,相加得 3/6 并立即约分为 1/2;第 3 个分数先约分为 -1/2,与 1/2 相加分子归零得 0/2,经 gcd(0, 2) = 2 自动归一为标准最简形式 0/1;最后加上 3/8 得最终答案 3/8。)

本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群: 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于