求最大公约数

在 C++17 及之后的版本中，标准库中引入了一个内置的 gcd 函数，用于计算两个整数的最大公约数（GCD）。它位于 <numeric> 头文件中，并使用欧几里得算法来高效地计算 GCD。

使用方法：

该函数位于 std 命名空间下，函数签名如下：
```
template <class T>
T gcd(T a, T b);
```
该模板函数可以接受任意整数类型的参数，包括 int、long、long long 等。

示例代码：

#include <iostream>
#include <numeric>  // 包含 gcd 函数
#include <vector>

int main() {
    int a = 56;
    int b = 98;

    // 使用 C++17 的内置 gcd 函数
    int result = std::gcd(a, b);
    std::cout << "GCD of " << a << " and " << b << " is " << result << std::endl;

    return 0;
}

输出：

GCD of 56 and 98 is 14

特点和优点：

高效实现：std::gcd 函数使用的是经过优化的欧几里得算法，能够高效地计算两个整数的最大公约数。
支持的类型：它支持任意整数类型，包括有符号和无符号的整数类型。
C++ 标准库保证：因为是标准库提供的函数，能确保跨平台的兼容性和性能优化。

使用范围：

你可以使用 std::gcd 来计算各种整数类型的 GCD，包括 int、long、long long，甚至自定义类型，只要它们遵循整数类型的基本规则。

示例：结合多个数的 GCD

你可以利用 std::gcd 来计算多个数的 GCD。假设我们想要计算一个数组中所有元素的 GCD，可以像这样结合 std::gcd 和 std::accumulate：

#include <iostream>
#include <numeric>  // 包含 gcd 和 accumulate 函数
#include <vector>

int main() {
    std::vector<int> nums = {56, 98, 42};

    // 使用 accumulate 来计算多个数的 GCD
    int result = std::accumulate(nums.begin(), nums.end(), nums[0], std::gcd<int, int>);

    std::cout << "GCD of the array is " << result << std::endl;

    return 0;
}

输出：

GCD of the array is 14

在c语言中也可以这样实现

在标准的 C 语言库中（如 stdio.h 或 stdlib.h），没有内置的 gcd 函数。因此，如果需要在 C 语言中计算两个整数的最大公约数（GCD），你需要自己编写该函数。

代码：

long long gcd(long long a,long long b)
{
    while(a != b)
    {
        if(a > b)
        {
            a = a - b;
        }
        else
        {
            b = b - a;
        }
    }
    return a;  // 返回a或b，因为最后它们相等并且是GCD
}

在每次循环中通过减法逐步接近两个数的最大公约数，源于“更相减损术”的原理。这种方法可以追溯到古代的数学家欧几里得，并且可以用来证明两个数的最大公约数在减法中逐渐逼近。

这段代码的目的是计算两个数 a 和 b 的最大公约数（GCD，Greatest Common Divisor）以下是对代码的解释：

while 循环执行的是一种较原始的 GCD 计算方法，称为“减法法”。它通过逐步减少两个数的值直到它们相等。
- 在每次循环中，它比较 aa 和 bb 的大小。如果 aa 大于 bb，就用 aa - bb 更新 aa，否则用 bb - aa 更新 bb。最终，aa 和 bb 会变成相等的数，而这个数就是它们的最大公约数。

原理：

假设我们有两个数 a 和 b，且 a > b。在减法法中，我们每次用较大的数减去较小的数，直到两个数相等。以下是这种方法的核心思想：

保持最大公约数不变：
- 设 d 是 a 和 b 的最大公约数，即 d = gcd(a, b)，这意味着 a 和 b 都可以被 d 整除（即 a = d * m，b = d * n，其中 m 和 n 是整数）。
- 当我们用较大的数 a 减去较小的数 b 后，得到的新数 a' = a - b。
- 注意到 a' = a - b 仍然可以被 d 整除，因为：
  [
  a' = a - b = d m - d n = d * (m - n)
  ]
  所以 a' 也是 d 的倍数，仍然与 b 有相同的最大公约数。
收敛到最大公约数：
- 在每次减法后，新的数对 (a', b) 或 (a, b') 的差值越来越小。最终，两个数会变得相等，而这个相等的数就是 a 和 b 的最大公约数。
- 由于在每次减法中，两个数的最大公约数保持不变，最终我们得到的相等数（即 aa = bb）就是它们的最大公约数。

举例说明：

假设 a = 24，b = 18，我们通过每次减法逐步计算最大公约数：

第一次循环：a = 24, b = 18，因为 a > b，所以 a = a - b = 24 - 18 = 6。
第二次循环：a = 6, b = 18，因为 b > a，所以 b = b - a = 18 - 6 = 12。
第三次循环：a = 6, b = 12，因为 b > a，所以 b = b - a = 12 - 6 = 6。
最后，a = b = 6，所以最大公约数是 6。

每一步中，最大公约数一直保持不变，直到最后两个数相等为止，而这个相等的数就是最大公约数。

优化：

实际计算 GCD 可以使用 欧几里得算法，它比这种减法法更高效。改进后的代码如下：

递归实现的代码示例：

long long gcd(long long a,long long b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);  // 欧几里得算法
}

迭代实现的代码示例：

除了递归，你也可以用迭代的方式实现：

#include <iostream>

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

解释：

欧几里得算法的原理是通过递归地使用模运算来逐步缩小问题规模，直到其中一个数为 0。此时，另一个数就是它们的最大公约数。
在循环中，a % b 计算出 a 除以 b 的余数，接着交换 a 和 b 的值，继续计算，直到 b 为 0。

这个实现方法比使用减法的方式更高效，尤其对于较大的数。

欧几里得算法（Euclidean algorithm）是一个用于计算两个整数的最大公约数（GCD，Greatest Common Divisor）的经典算法。它的基本原理是基于一个非常重要的数学定理：

定理：

若 d 是 a 和 b 的最大公约数，则 d 也是 b 和 a % b 的最大公约数。

证明：

设 a 和 b 是两个整数，且 a > b，则可以写成如下的关系：
a = b * q + r
其中：

q 是商（整数），
r 是余数，即 r = a % b。

根据这个关系式，可以重写为：
r = a - b * q

现在，让我们从 d = gcd(a, b) 出发进行推导，假设 d 是 a 和 b 的最大公约数。根据最大公约数的定义：

d 可以整除 a，即 a = d * m，其中 m 是某个整数。
d 也可以整除 b，即 b = d * n，其中 n 是某个整数。

接下来，我们要证明 d 也可以整除 r（即 a % b）。根据前面的等式：
r = a - b * q
代入 a = d * m 和 b = d * n：
r = d m - (d n) * q
r = d (m - n q)

因此，r 是 d 的倍数，这说明 d 也整除 r。

结论：

因为 d 整除 b，并且 d 也整除 r，根据最大公约数的定义，d 是 b 和 r 的公约数。
因此，d = gcd(b, r)，而 r = a % b，这就证明了：
gcd(a, b) = gcd(b, a % b)

这个过程可以重复，直到余数为 0。此时，剩下的数就是 a 和 b 的最大公约数。

算法原理：

给定两个整数 a 和 b，其中 a > b。
根据定理，gcd(a, b) 等于 gcd(b, a % b)。换句话说，较大的数 a 可以被较小的数 b 除尽，并且我们继续用 a 除以 b 的余数来替换 a。
不断重复这个过程，将 b 和 a % b 作为新的一对数，直到其中一个数变为 0。
当其中一个数为 0 时，另一个数就是它们的最大公约数。

欧几里得算法的核心思想是基于一个重要的数学定理，这个定理解释了为什么最大公约数（GCD）可以通过 a 和 b 转换为 b 和 a % b 来计算。下面是这个定理的详细解释。

总结：

在欧几里得算法中，我们通过每次将 a 替换为 a % b，并不断计算余数，最终将问题缩小。
由于最大公约数 d 可以同时整除 b 和 a % b，因此 gcd(a, b) 可以递归地转换为 gcd(b, a % b)。
最终，当余数为 0 时，b 就是 a 和 b 的最大公约数。

这个定理和算法的关键在于利用了“除法余数不影响公约数”的特性，使得我们可以通过递归或迭代高效地计算出最大公约数。

欧几里得算法的优点：

高效：每一步都通过取模运算来减少较大数的大小，快速缩小问题的规模。相比于简单的逐个枚举约数，欧几里得算法能在对数时间内找到最大公约数。
简单实现：该算法只需要简单的取模运算，容易实现且计算量小。

另：求最小公倍数的方法：
另两数相乘然后除以最大公约数。
tip：为了防止爆int可以先除，再乘。

当前页面是本站的「Google AMP」版。查看和发表评论请点击：完整版 »