欧几里得算法模板

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

// 递归写法
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代写法
int gcd2(int a, int b) {
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}

// LCM = a / gcd(a,b) * b（先除后乘防溢出）
long long lcm(int a, int b) {
    return (long long)a / gcd(a, b) * b;
}

// 扩展欧几里得：求 ax + by = gcd(a,b) 的解
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

int main() {
    cout << gcd(12, 18) << endl;   // 6
    cout << lcm(12, 18) << endl;   // 36

    long long x, y;
    exgcd(35, 15, x, y);  // 35x+15y=5
    cout << x << " " << y << endl;  // 1 -2
    return 0;
}

📖 要点说明

• gcd(a,b) = gcd(b, a%b)，递归到 b=0 返回 a
• LCM 一定先除后乘：a/gcd*b 防溢出
• 扩展欧几里得可求逆元、解方程

⚠️ 常见错误

• LCM 先乘后除溢出：a*b/gcd 中间结果可能超 long long
• gcd 参数为 0 时的处理
• 扩展欧几里得中 x,y 的赋值方向