33DAI：导入1个版本

2026-05-20T18:12:11Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本	2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:39Z

导入1个版本

←上一版本	2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

== 最大公因数（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:三三文档]]

06-数学相关/02-最大公因数与最小公倍数 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档