当前位置:首页 > 文章列表 > Golang > Go问答 > Go math/big.Int.GCD 怎样计算大整数的最大公约数

Go math/big.Int.GCD 怎样计算大整数的最大公约数

来源:17golang原创 2026-11-19 04:37:21 0浏览 收藏

处理订单号、分数分母或协议参数时,两个整数可能早已超过 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 都不小于零。

大整数 a 和 b 进入 Int.GCD 并得到最大公约数 z 与 Bézout 系数 x y 的结构图
图1:GCD 参数与结果的静态说明图;它展示输入、结果和系数之间的关系,不是运行截图或执行证据。

可以把这组参数记成一张小表:

参数作用调用后的含义
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 之前保留输入层的存在性信息。

GCD 对零值和边界输入的静态关系图,展示 z 等于绝对值或零以及可选系数
图2:零值与负数边界的静态说明图;它帮助区分输入状态和 GCD 输出,不是运行截图或执行证据。

需要系数时读取 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 最值得保留的三个边界。

版本声明
本文转载于:17golang原创 如有侵犯,请联系study_golang@163.com删除
Go http.Request.PostFormValue 怎样读取 POST 表单字段Go http.Request.PostFormValue 怎样读取 POST 表单字段
上一篇
Go http.Request.PostFormValue 怎样读取 POST 表单字段
Go xml.Decoder.Entity 怎样自定义 XML 实体替换
下一篇
Go xml.Decoder.Entity 怎样自定义 XML 实体替换
查看更多
最新文章
查看更多
课程推荐
  • 前端进阶之JavaScript设计模式
    前端进阶之JavaScript设计模式
    设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
    543次学习
  • GO语言核心编程课程
    GO语言核心编程课程
    本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
    516次学习
  • 简单聊聊mysql8与网络通信
    简单聊聊mysql8与网络通信
    如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
    500次学习
  • JavaScript正则表达式基础与实战
    JavaScript正则表达式基础与实战
    在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
    487次学习
  • 从零制作响应式网站—Grid布局
    从零制作响应式网站—Grid布局
    本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
    485次学习
查看更多
AI推荐
  • PubMedQA数据集详解:生物医学问答基准、功能与应用指南
    PubMedQA
    深入了解PubMedQA生物医学问答数据集,涵盖其核心功能、使用方法及在临床决策、药物研发等场景的应用,助力提升NLP模型性能。
    1102次使用
  • H2O EvalGPT:开源LLM大模型评估与排行榜工具
    H2O EvalGPT
    H2O EvalGPT是H2O.ai推出的开源LLM评估平台,提供详细的大模型性能排行榜、行业特定基准测试及A/B测试功能,助您快速选择最适合项目的高性能大语言模型。
    1098次使用
  • LMArena是什么?伯克利AI模型评估平台使用指南与功能解析
    LMArena
    LMArena是加州大学伯克利分校推出的AI模型匿名评测平台。通过盲测投票机制,用户可对比不同大模型回答并生成实时排行榜,助力开发者优化模型及用户选择最佳AI工具。
    1268次使用
  • 斯坦福HELM:大语言模型Holistic Evaluation整体评估框架详解
    HELM
    深入了解斯坦福推出的HELM(Holistic Evaluation of Language Models)大模型评测体系。本文解析其核心功能、安装配置步骤及应用场景,涵盖准确性、公平性、鲁棒性等多维度指标,助力开发者全面优化语言模型性能。
    1209次使用
  • MMBench详解:多模态大模型基准测试、功能特点与使用指南
    MMBench
    MMBench是由上海人工智能实验室等机构联合推出的多模态基准测试平台,提供细粒度能力评估、大规模数据集及VLMEvalKit工具。本文详细介绍其核心功能、安装使用方法及应用场景,助力开发者全面评估多模态模型性能。
    1056次使用
微信登录更方便
  • 密码登录
  • 注册账号
登录即同意 用户协议 和 隐私政策
返回登录
  • 重置密码