【20240106】leetcode 2807. 在链表中插入最大公约数

2807. 在链表中插入最大公约数 - 力扣（LeetCode）

最大公约数（GCD，Greatest Common Divisor）是两个或多个整数的共有因数中的最大值。也叫作最大公因数、最大公因子或最大公量。如果两个整数的最大公约数是 1，那么它们被称为互质。

计算两个整数的最大公约数有多种方法，其中最著名的方法之一是辗转相除法（Euclidean Algorithm）。辗转相除法的基本思想是通过反复应用两个整数的除法余数关系，直到余数为零为止。具体步骤如下：

1. 用较大的数除以较小的数，得到余数。
2. 将较小的数作为新的被除数，余数作为新的除数。
3. 重复步骤 1 和 2，直到余数为零。
4. 最后的非零余数即为最大公约数。

这个算法的效率很高，时间复杂度为 �(log⁡(min⁡(�,�)))O(log(min(a,b)))。

以下是一个用 Go 语言实现的最大公约数的辗转相除法示例：

package main

import "fmt"

// 辗转相除法求最大公约数
func gcd(a, b int) int {
    for b != 0 {
        temp := b
        b = a % b
        a = temp
    }
    return a
}

func main() {
    num1 := 48
    num2 := 18

    result := gcd(num1, num2)

    fmt.Println("最大公约数为:", result)
}

在这个例子中，gcd 函数使用了辗转相除法来计算两个整数的最大公约数。