查看“︁06-数学相关/02-最大公因数与最小公倍数”︁的源代码


== 最大公因数（GCD） ==

=== 递归写法 ===

<syntaxhighlight lang="cpp">
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
</syntaxhighlight>

=== 迭代写法 ===

<syntaxhighlight lang="cpp">
int gcd(int a, int b)
{
    while (b)
    {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}
</syntaxhighlight>

=== C++ 内置函数 ===

<syntaxhighlight lang="cpp">
cout << __gcd(a, b); // 比赛时可以用
</syntaxhighlight>

== 最小公倍数（LCM） ==

<math>\operatorname{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}</math>

<syntaxhighlight lang="cpp">
int lcm(int a, int b)
{
    return a / gcd(a, b) * b; // 先除后乘，防止溢出
}
</syntaxhighlight>

== 扩展欧几里得算法 ==

求 <math>ax+by=\gcd(a,b)</math> 的一组整数解 <math>(x,y)</math>。

<syntaxhighlight lang="cpp">
// 返回 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};
}
</syntaxhighlight>

引用版本（返回 gcd）：

<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

=== 通解 ===

当求出来一组 <math>Ax+By=C</math> 的解 <math>x_0,y_0</math> 后，通解为：

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

== 更多数的 GCD/LCM ==

<syntaxhighlight lang="cpp">
int ans = a[1];
for (int i = 2; i <= n; i++)
    ans = gcd(ans, a[i]);
</syntaxhighlight>


[[Category:数学相关]]
[[Category:三三文档]]