Go math/big.Int.GCD 怎样计算大整数的最大公约数
来源:17golang原创
时间:2026-11-19 04:37:21 242浏览 收藏
处理订单号、分数分母或协议参数时,两个整数可能早已超过 int64 的范围。此时仍可以先把它们解析成 math/big.Int,再调用 GCD 计算最大公约数。最容易写错的地方有三个:接收者 z 会被原地改写、负数的符号不会保留到 GCD 结果中,以及只有传入 x、y 时才会得到 Bézout 系数。
最小调用是new(big.Int).GCD(nil, nil, a, b)。返回的整数总是非负;如果还需要证明关系,再传入两个独立的big.Int接收者,让结果满足z = a*x + b*y。
先看 GCD 的参数和返回值
math/big.Int.GCD 的完整签名是:
// z 接收最大公约数,x 和 y 可选接收 Bézout 系数。 func (z *Int) GCD(x, y, a, b *Int) *Int
其中 a 和 b 是参与计算的两个大整数,z 保存最大公约数。x、y 可以传 nil;只要需要系数,就应该同时传入两个接收者,因为它们共同描述线性组合关系。官方文档规定,无论输入正负,z 都不小于零。

可以把这组参数记成一张小表:
| 参数 | 作用 | 调用后的含义 |
|---|---|---|
z | 结果接收者 | gcd(a,b),始终为非负数 |
x、y | 可选系数接收者 | 满足 z = a*x + b*y |
a、b | 输入整数 | 允许为正数、负数或零 |
用 math/big.Int 计算大整数 GCD
下面的例子把十进制字符串解析为大整数,并只接收最大公约数。示例故意把 z 单独创建出来,不把输入对象当作结果接收者;这样读代码时更容易确认哪些值会被改写。
package main
import (
"fmt"
"log"
"math/big"
)
func main() {
a, ok := new(big.Int).SetString("123456789012345678901234567890", 10)
if !ok {
log.Fatal("a 不是合法的十进制整数") // 解析失败时不要继续使用空指针。
}
b, ok := new(big.Int).SetString("98765432109876543210", 10)
if !ok {
log.Fatal("b 不是合法的十进制整数") // 输入来自文本时必须保留解析错误。
}
z := new(big.Int).GCD(nil, nil, a, b) // nil 表示本次只需要最大公约数。
fmt.Println(z.String()) // String 负责把大整数格式化为十进制文本。
}
这里的 SetString 返回两个值:大整数指针和是否解析成功。GCD 返回的就是 z,所以也可以继续调用 z.BitLen()、z.Cmp 等方法做后续判断。
负数和零值要怎样理解
GCD 处理的是公约数的非负代表值。输入带负号时,结果仍然非负;输入为零时,边界规则也很明确:
a = 0且b != 0时,z = |b|。a != 0且b = 0时,z = |a|。a = 0且b = 0时,z = 0。
因此,业务代码不应该用“结果为零”来判断输入是否解析失败;零是合法输入组合的结果。若需要区分“用户没有提供数字”和“用户提供了 0”,应在进入 big.Int 之前保留输入层的存在性信息。

需要系数时读取 Bézout 等式
如果程序不仅要知道最大公约数,还要保留一组线性组合系数,可以把 x、y 作为接收者传入。返回后应检查等式,而不是只打印某个系数猜测其含义。
package main
import (
"fmt"
"math/big"
)
func main() {
a := new(big.Int).SetInt64(-84)
b := new(big.Int).SetInt64(30)
z, x, y := new(big.Int), new(big.Int), new(big.Int)
z.GCD(x, y, a, b) // 同时写入 z、x、y,三者都应使用独立接收者。
left := new(big.Int).Mul(a, x) // 计算 a*x,避免改写输入 a。
left.Add(left, new(big.Int).Mul(b, y)) // 再加上 b*y,验证 Bézout 等式。
fmt.Printf("z=%s, x=%s, y=%s, a*x+b*y=%s\n", z, x, y, left)
}
对负数输入,x 或 y 的符号可能随输入变化,但等式仍应成立。系数是该组输入的一种解,不要把它当成唯一解,也不要在没有业务需要时为每次 GCD 都分配两个额外的大整数。
避免 Int 复制,也不要把 GCD 和 ModInverse 混用
big.Int 是带内部表示的多精度整数,官方文档不支持通过浅复制来复制它的数值。需要保留一份值时,使用 new(big.Int).Set(src) 或其他明确的设置方法,并让每个逻辑值拥有自己的接收者。
func copyInt(src *big.Int) *big.Int {
dst := new(big.Int).Set(src) // Set 做数值复制,避免直接复制 Int 结构体。
return dst
}
还要区分两个相似但不同的任务:GCD(a,b) 求的是最大公约数;ModInverse(g,n) 求的是模环中的逆元,互质条件不满足时可能返回 nil。不要因为都涉及“整除关系”就用一个 API 替换另一个。
常见问题
GCD 的结果为什么总是正数或零?
它使用最大公约数的非负代表值。负数输入不会让 z 变成负数。
x 和 y 可以只传一个吗?
不建议。它们共同表示 z = a*x + b*y,需要系数时应同时提供两个独立接收者。
两个输入都是零会 panic 吗?
不会。官方边界定义是 z = x = y = 0(当系数接收者被提供时)。
小结
面对超出内置整数范围的最大公约数计算,先用 SetString 得到独立的 big.Int 输入,再用独立的 z 调用 GCD。只求结果时把 x、y 设为 nil;需要证明线性组合时同时接收两个系数。最后记住:结果的非负性、零值规则和 Int 不能浅复制,是这段 API 最值得保留的三个边界。
-
369 收藏
-
344 收藏
-
464 收藏
-
327 收藏
-
349 收藏
-
Golang · Go问答 | 25分钟前 | 标准库 · Context · 并发控制 · net/http · Go问答 · Go 请求超时 handler 取消信号 ErrHandlerTimeout Request.Context http.TimeoutHandler311 收藏
-
389 收藏
-
Golang · Go问答 | 31分钟前 | 错误处理 · 重定向 · net/http · HTTP客户端 · Go问答 · Go net/http error response CheckRedirect http.Client.Do ErrUseLastResponse164 收藏
-
Golang · Go问答 | 33分钟前 | 网络编程 · TCP · Go问答 · Go KeepAliveConfig SetKeepAlivePeriod net.TCPConn.SetKeepAlive TCP keep-alive474 收藏
-
181 收藏
-
339 收藏
-
Golang · Go问答 | 52分钟前 | 文件处理 · csv · Go问答 · 错误排查 · Go encoding/csv csv.Reader CSV读取 FieldsPerRecord ErrFieldCount210 收藏
-
170 收藏
-
440 收藏
-
128 收藏
-
Golang · Go问答 | 58分钟前 | JSON · 类型转换 · Go问答 · encoding/json · Go encoding/json json.Unmarshal float64 json.Number JSON数字 Decoder.UseNumber397 收藏
-
333 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 543次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 516次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 500次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 485次学习