GCD与LCM算法详解：从欧几里得到竞赛应用

1. 数论基础：最大公约数与最小公倍数

在算法竞赛和编程面试中，数论问题出现的频率相当高。其中最大公约数(GCD)和最小公倍数(LCM)是最基础也是最重要的概念之一。这两个概念不仅在数学问题中广泛应用，在解决实际问题时也经常作为关键步骤出现。

理解GCD和LCM的关系是掌握数论的第一步。简单来说，两个数的乘积等于它们的GCD和LCM的乘积。用公式表示就是：a × b = GCD(a,b) × LCM(a,b)。这个关系式为我们计算LCM提供了便利，因为通常计算GCD要比直接计算LCM容易得多。

2. 欧几里得算法详解

2.1 算法原理与证明

欧几里得算法（又称辗转相除法）是计算两个数最大公约数的高效方法。其基本原理基于以下数学定理：对于任意两个正整数a和b，有GCD(a,b) = GCD(b, a mod b)。这个定理可以通过数学归纳法严格证明。

算法的终止条件是当b变为0时，此时的a就是所求的最大公约数。这个算法的美妙之处在于它每次递归或迭代都将问题的规模至少减小一半，因此时间复杂度是O(log min(a,b))，效率非常高。

2.2 代码实现与优化

基础版本的递归实现如下：

cpp复制LL gcd(LL a, LL b) {
    if(!b) return a;
    return gcd(b, a % b);
}

在实际编程中，我们还可以进行一些优化：

1. 使用迭代而非递归实现，避免栈溢出风险：

cpp复制LL gcd(LL a, LL b) {
    while(b) {
        LL t = b;
        b = a % b;
        a = t;
    }
    return a;
}

2. 对于大整数运算，可以使用更高效的二进制GCD算法（Stein算法），它避免了耗时的取模运算，转而使用位移和减法操作。

3. 在C++17及以上版本中，可以直接使用标准库中的std::gcd和std::lcm函数。

注意：当处理负数时，GCD的结果应该是正数。因此在实际实现中，应该先对输入取绝对值。

3. 最小公倍数的计算与应用

3.1 LCM的计算方法

根据GCD和LCM的关系，我们可以很容易地得到计算LCM的公式：