06-数学相关/02-最大公因数与最小公倍数

最大公因数（GCD）

递归写法

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

迭代写法

int gcd(int a, int b)
{
    while (b)
    {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

C++ 内置函数

cout << __gcd(a, b); // 比赛时可以用

最小公倍数（LCM）

[math]\displaystyle{ \operatorname{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)} }[/math]

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

扩展欧几里得算法

求 [math]\displaystyle{ ax+by=\gcd(a,b) }[/math] 的一组整数解 [math]\displaystyle{ (x,y) }[/math]。

// 返回 ax+by=gcd(a,b) 的解 (x,y)
pair<int, int> exGCD(int a, int b)
{
    if (b == 0)
        return {1, 0};
    auto [xx, yy] = exGCD(b, a % b);
    return {yy, xx - a / b * yy};
}

引用版本（返回 gcd）：

int exGcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int xx, yy;
    int gcd = exGcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return gcd;
}

通解

当求出来一组 [math]\displaystyle{ Ax+By=C }[/math] 的解 [math]\displaystyle{ x_0,y_0 }[/math] 后，通解为：

[math]\displaystyle{ x=x_0+\frac{B}{\gcd(A,B)}\cdot k }[/math] [math]\displaystyle{ y=y_0-\frac{A}{\gcd(A,B)}\cdot k }[/math]

更多数的 GCD/LCM

int ans = a[1];
for (int i = 2; i <= n; i++)
    ans = gcd(ans, a[i]);