GCD 与 LCMCSP-J

💡 核心思想

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

🎯 直觉理解

最大公约数（GCD）用辗转相除法：$gcd(a,b)=gcd(b,a%b)$。直观理解：a 和 b 的最大公约数，和 b、a 除以 b 的余数的最大公约数相同——因为余数 = a - 商乘 b，a、b 的任何公约数都整除余数。

辗转相除每次取模，规模至少减半，$O(log n)$，几千亿的数也瞬间算完。

LCM：$lcm(a,b)=a/gcd(a,b) imes b$（先除再乘防溢出）。gcd 的性质常用：gcd 有交换结合律、多个数一起取 gcd 可以边读边取。竞赛里 gcd 是"基础设施"，很多题的第一行就是它。

📝 算法流程

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 
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;
}

⚠️ 常见坑点

📚 相关题目