最大公约数与最小公倍数

在ACM竞赛中，最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)是非常基础且常用的数学概念。这些算法在整数理论、分数计算、密码学等多种问题中扮演着重要角色。

基础概念

【最大公约数】

最大公约数(GCD)是指能够同时整除两个或多个整数的最大正整数。例如，12和18的最大公约数是6，因为6是能同时整除12和18的最大整数。

【最小公倍数】

最小公倍数(LCM)是指能够被两个或多个整数同时整除的最小正整数。例如，12和18的最小公倍数是36，因为36是能同时被12和18整除的最小正整数。

欧几里得算法(辗转相除法)

算法原理

欧几里得算法基于一个重要性质：如果a和b是两个正整数，且a > b，那么gcd(a, b) = gcd(b, a % b)。

这一性质使我们可以递归地将问题规模缩小，直到其中一个数为0时，另一个数就是最大公约数。

代码实现

递归版本

// 递归实现欧几里得算法
int gcd(int a, int b) {
    if (b == 0) return a;  // 基础情况：当b为0时，a即为最大公约数
    return gcd(b, a % b);  // 递归调用：将b和a%b作为新的输入
}

迭代版本

// 迭代实现欧几里得算法
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;  // 计算余数
        a = temp;   // 更新a为原来的b
    }
    return a;  // 当b为0时，a即为最大公约数
}

时间复杂度分析

欧几里得算法的时间复杂度为O(log(min(a, b)))。这是因为每次迭代后，较小数至少减半，所以最多需要O(log N)步就可以计算出结果。

最小公倍数计算

最小公倍数可以通过最大公约数来计算：lcm(a, b) = (a * b) / gcd(a, b)。

但在实际编程中，为了避免整型溢出，我们通常这样写：

int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 先除后乘，避免溢出
}

扩展欧几里得算法

如果我们需要解决形如ax + by = gcd(a, b)的方程，可以使用扩展欧几里得算法。

// 扩展欧几里得算法，计算ax + by = gcd(a, b)的一组解
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

这里，函数返回gcd(a, b)的值，并通过引用更新x和y，使它们满足等式ax + by = gcd(a, b)。

应用场景

  1. 分数运算：通分、约分等操作
  2. 求解模线性方程：如解模意义下的逆元
  3. 裴蜀定理应用：判定同余方程的可解性
  4. 互质判定：判断两数是否互质(gcd = 1)

例题分析

例题1：分数加减法

在处理分数运算时，常需要先通分（求LCM），再进行加减，最后约分（求GCD）。

struct Fraction {
    int num, den;  // 分子(numerator)和分母(denominator)

    // 约分，使分数保持最简形式
    void simplify() {
        int g = gcd(abs(num), den);
        num /= g;
        den /= g;
    }

    // 分数加法
    Fraction add(Fraction other) {
        int lcm_val = lcm(den, other.den);
        int new_num = num * (lcm_val / den) + other.num * (lcm_val / other.den);
        Fraction result = {new_num, lcm_val};
        result.simplify();
        return result;
    }
};

例题2：互质数对计数

给定n，求[1, n]区间内互质数对(i, j)的个数（1 ≤ i < j ≤ n）。

int countCoPrimePairs(int n) {
    int count = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (gcd(i, j) == 1) {
                count++;
            }
        }
    }
    return count;
}

优化方法：通过欧拉函数和容斥原理可以在O(n log n)时间内解决。

常见易错点

  1. 整数溢出：计算LCM时先乘后除可能导致整数溢出，应当先除后乘
  2. 负数处理：GCD算法需确保传入的是非负数，或在算法中进行适当处理
  3. 零的特例：注意处理涉及零的情况，如gcd(0, n) = n

竞赛优化技巧

  1. 使用C++17的内置函数：std::gcd(a, b)和std::lcm(a, b)（在<numeric>头文件中）
  2. 对于多个数的GCD，可以利用结合律依次计算
  3. 在需要频繁计算GCD的场景，可以通过预处理优化

习题推荐

  1. USACO - Cow GCD：计算一系列数字的GCD
  2. CodeForces - GCD Compression：涉及GCD性质的构造问题
  3. LeetCode 1071. Greatest Common Divisor of Strings：字符串的GCD应用

总结

最大公约数和最小公倍数是竞赛编程中不可或缺的基本工具。掌握欧几里得算法及其扩展形式，可以帮助你解决各类整数理论问题。记住，这些算法不仅高效，而且实现简单，是必须熟练掌握的基础算法。