C++如何计算两个大整数的公约数（辗转相除法）-C++-PHP中文网

大整数需用vector（低位在前）模拟运算，避免溢出；核心实现subtract、compare、mod三函数，mod优先用long long快速取模；gcd必须迭代实现并复用内存，防止栈溢出和拷贝开销。

c++如何计算两个大整数的公约数（辗转相除法）

大整数不能直接用 `int` 或 `long long` 怎么办

标准整型根本存不下上百位的数字，std::gcd 和取模运算会直接溢出或编译失败。必须用字符串或数组模拟大数运算，核心是把“除法”拆成“减法+比较”，避免真实除法——因为大数除法实现复杂且易错，而辗转相除法本质只需要 a % b，而 a % b 可以用重复减法等价替代（尤其当 b 相对较小时），但更通用的做法是实现大数取模。

实际中推荐用 std::vector<int></int> 存储十进制各位（低位在前），再手写 subtract、compare、mod 三个基础函数。不建议用字符串做数值计算——每次都要遍历转换，效率低且边界多。

存储格式统一用低位在前，比如 "123" 存为 {3,2,1}，方便进位和对齐
compare(a, b) 返回 -1/0/1，比大小时不依赖完整减法
mod(a, b) 不要真做除法：先估算商的位数，用移位（即乘10的幂）逼近，再试减；或者直接循环减（仅适用于 b 不太大）

为什么不能直接递归调用 `gcd(a, b)` 求大数

递归深度不可控，两个百位数反复取模可能迭代上百次，栈容易爆；更重要的是，每次调用都要拷贝整个大数对象（如 vector），开销巨大。必须改用迭代写法，并复用内存（例如原地修改 a 和 b 的存储容器）。

标准辗转相除法公式是：gcd(a,b) = gcd(b, a % b)，但对大数来说，a % b 是性能瓶颈。如果 a 比 b 大很多（比如 a 有 100 位，b 只有 5 位），可以先做一次快速模：用 long long 把 b 转成整数，再用字符串逐位取模（类似秦九韶算法），省去完整大数模运算。

当 b 的位数 ≤ 18（能放进 unsigned long long），优先用字符串转整型 + 逐位取模：res = (res * 10 + digit) % b_val
否则才走完整大数模逻辑
迭代时用 swap(a, b) 避免拷贝，循环条件是 !is_zero(b)

`subtract` 实现里最容易漏掉的借位细节

大数减法不是简单 for 循环每位相减。常见错误是：没处理前导零导致后续比较失败；借位跨多位时只减了一次 1；或者没判断被减数是否小于减数就硬减，结果变负数却没报错。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

正确做法是先用 compare 判定大小，确保调用 subtract(large, small)；然后从低位开始，维护一个 carry = 0，每位计算 digit = large[i] - small[i] - carry，若 digit ，则 <code>digit += 10 且 carry = 1；最后去掉结果末尾所有 0（注意保留一个 0 表示零值）。

必须在 subtract 后调用 trim_leading_zeros()，否则 compare 会误判长度
借位变量 carry 类型用 int 即可，不可能超过 1
如果 small 位数更少，补零到相同长度再减，别用 if 分支判断索引越界

测试时发现 `gcd("0", "123")` 返回空或崩溃怎么办

边界情况几乎必出错：输入含前导零的字符串（如 "00123"）、全零、一零一非零、空串。标准 gcd 定义中 gcd(0, x) = |x|，所以 gcd(0, 123) = 123，但你的大数类若没显式处理 0，mod(a, b) 可能除零或陷入死循环。

务必在入口处做标准化：解析字符串时跳过前导零，结果为空则设为单个 0；在 gcd 主循环开头加判断：if is_zero(a) return b; if is_zero(b) return a;。另外，is_zero() 不能只看长度，要遍历确认所有位都是 0。

构造函数里就做 trim_leading_zeros()，避免后续处处检查
mod(a, b) 前必须 if (is_zero(b)) throw std::invalid_argument("mod by zero");
测试用例至少覆盖：gcd("0","0")（应返回 "0"）、gcd("1000000","1")、gcd("12345678901234567890","987654321")

实际写下来会发现，最难的不是算法逻辑，而是把每一个“显然”的操作（比如“减法”“比较”“取模”）都抠到内存布局和边界上。很多人卡在 subtract 返回后多了一个 0，或者 compare 因长度判断错导致 mod 算出负余数——这些不会报编译错误，但 gcd 结果完全不对。