数论基础笔记：最大公约数（GCD）与最小公倍数（LCM）

一、最大公约数（Greatest Common Divisor, GCD）

定义：两个整数共有约数中最大的那个数。

方法1：辗转相除法（欧几里得算法）

核心定理：$\boldsymbol{\gcd(a, b) = \gcd(b, a \bmod b)}$
（两个数的最大公约数 = 较小数与两数余数的最大公约数）

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, t;
    cin >> a >> b;
    if (b > a) swap(a, b); // 确保a ≥ b（非必须，取模会自动处理）
    while (1) {
        t = a % b;
        if (t == 0) break; // 余数为0时，b即为GCD
        a = b;
        b = t;
    }
    cout << b;
    return 0;
}

特点：

• 时间复杂度：$\boldsymbol{O(\log \min(a, b))}$，效率极高。
• 无需提前比较大小，自动适配 $a < b$ 的情况。

方法2：内置函数 __gcd(x, y)

说明：C++ algorithm 头文件提供的现成函数，直接返回GCD。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << __gcd(a, b) << endl;
    return 0;
}

注意事项：

• 支持 int、long long 类型，但两参数类型必须相同。
• 禁止用浮点型，浮点数需手写GCD函数。
• 头文件：#include <algorithm>（或万能头 bits/stdc++.h）。

方法3：常规枚举法（易超时）

思路：从两数较小值向下枚举，找到第一个能同时整除两数的数。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (int i = min(a, b); i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            cout << i;
            break;
        }
    }
    return 0;
}

特点：

• 时间复杂度：$\boldsymbol{O(\min(a, b))}$，大数据（如 $10^9$）会超时，仅适合小范围验证。

二、最小公倍数（Least Common Multiple, LCM）

定义：两个整数公有倍数中最小的那个数。

方法1：常规枚举法（易超时）

思路：从两数较大值向上枚举，找到第一个能同时被两数整除的数。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (int i = max(a, b); i <= a * b; i++) {
        if (i % a == 0 && i % b == 0) {
            cout << i;
            break;
        }
    }
    return 0;
}

特点：

• 时间复杂度高，大数据易超时，不推荐实用。

方法2：公式法（推荐）

核心公式：$\boldsymbol{\text{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}}$
（最小公倍数 = 两数乘积 ÷ 最大公约数）

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int gcd_val = __gcd(a, b);
    cout << 1LL * a * b / gcd_val; // 1LL防止a*b溢出int范围
    return 0;
}

特点：

• 时间复杂度：$\boldsymbol{O(\log \min(a, b))}$，效率极高。
• 关键提醒：若 $a, b$ 为 int，乘积可能溢出，需转 long long 计算。

方法3：倍数递增法

思路：设两数为 $m, n$，递增 $i$ 直到 $m \times i$ 能被 $n$ 整除，此时 $m \times i$ 即为LCM。

代码实现：

#include <stdio.h>

int main() {
    int m, n, i = 1;
    scanf("%d%d", &m, &n);
    while (m * i % n != 0) {
        i++;
    }
    printf("%d", m * i);
    return 0;
}

特点：

• 本质与公式法一致，适合C语言轻量场景。

三、核心总结对比表

类型	推荐方法	时间复杂度	适用场景
最大公约数	辗转相除法/__gcd	$O(\log \min(a,b))$	所有场景（尤其大数据）
最小公倍数	公式法（GCD推导）

关键避坑：

1. 计算LCM时务必注意整数溢出，优先用 long long 存储中间结果。
2. 内置函数 __gcd 严格要求两参数类型一致，浮点型需手写实现。