自动搬运

查看原文

来自洛谷，原作者为

	残阳如血 人事已尽，天命难违

搬运于2025-08-24 21:14:43，当前版本为作者最后更新于2023-09-29 20:34:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路分析

对于求 $\gcd(a,b,c)$，我们可以先求出 $k=\gcd(a,b)$，结果即为 $\gcd(k,c)$。

接下来介绍三种求最大公约数的方法。

辗转相除法

这里不带证明的给出：

$$\gcd(a,b) = \begin{cases} a &b=0 \cr \gcd(b,a\mod b) &b\not=0 \end{cases} $$

根据递归式一路递归即可。

对于没有构造的数据，这种方法的时间复杂度基本是 $\Theta(1)$，但是最坏情况下的时间复杂度为 $\mathcal O(\log\max\{a,b\})$ 的。

更相减损法

对于一般的数据类型，辗转相除法的速度是比较快的，但是对于自己手写的高精度，取模运算会十分的慢，导致辗转相除法的效率大为降低。

所以我们可以用更相减损法来解决问题。但是需要注意这样的话运算次数会增加许多。

同样不带证明给出：

$$\gcd(a,b)=\begin{cases} a&a=b\\ \gcd(a-b,b)&a>b\\ \gcd(b-a,a)&a<b \end{cases} $$

STL 大法

在 <algorithm> 中，定义有一个函数 std::__gcd(a,b)，可以直接求出 $\gcd(a,b)$！

std::__gcd(a,b) 底层的实现应该是辗转相除法，所以时间复杂度是 $\mathcal O(\log\max\{a,b\})$。

代码演示

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int x, y, z;
	cin >> x >> y >> z;
	cout << __gcd(__gcd(x, y), z) << endl;
	return 0;
}