在 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可以先除，再乘。
的值会逐渐逼近 
（其中 γ\gammaγ 是欧拉常数，大约为 0.577）。