登录
推荐 文章 Go 技术 课程 下载 专题 AI
首页 >  Golang >  Go问答

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 都不小于零。

大整数 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删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>