GCD 与 LCMCSP-J

💡 核心思想

GCD（最大公约数）和 LCM（最小公倍数）是数论基础。辗转相除法（欧几里得算法）$O(\log \min(a,b))$ 求 GCD。扩展欧几里得算法可以求 $ax + by = \gcd(a,b)$ 的整数解。

🎯 直觉理解

GCD 就像找两个人共同拥有的"最大度量单位"。比如一段 12cm 和一段 18cm 的木条，你用 6cm 的尺子能量完它们（6 是 GCD）。LCM 则是"最小公共刻度"——12 和 18 的最小公倍数是 36，即 12×3 = 18×2 = 36。

📝 算法流程

1. 辗转相除：gcd(a,b) = gcd(b, a%b)，gcd(a,0) = a
2. LCM = a / gcd(a,b) * b
3. 扩展欧几里得：求 ax + by = gcd(a,b) 的解
4. 裴蜀定理：ax + by = c 有解当且仅当 gcd(a,b) | c

$$\gcd(a,b) = \gcd(b, a \bmod b)$$

$$\text{lcm}(a,b) = \frac{a \cdot b}{\gcd(a,b)}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a,b) * b; }
// 扩展欧几里得
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x = 1; y = 0; return a; }
    ll d = exgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
int main() {
    ll a, b; cin >> a >> b;
    cout << gcd(a,b) << endl;
    ll x, y; exgcd(a, b, x, y);
    cout << x << " " << y << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目