题解 SP27561 【GDCOFTI - Greatest Common Divisor Of Three Integers】
Ajwallet
·
·
题解
这题十分简单，用到的是辗转相除法的思想（一种快速求最大公因数的方法）
辗转相除法，又称欧几里得算法，其算法主体为：
gcd(x,y)=gcd(y,x\ mod\ y)
这里放一下欧几里德算法的题设及其证明
$$\forall a,b \in N,b \neq 0 \ \ gcd(a,b)=gcd(b,a\ mod\ b)$$
----
证明:
若$a<b$则$a\ mod\ b=a,\therefore gcd(a,b)=gcd(b,a)$，命题成立
若$a\geq b$，设$a=qb+r,0\leq r<b$，显然$r=a\ mod\ b$。设$d$为$a,b$的任意一个公约数$$\because d\mid a,d\mid qb,a\geq qb$$
$$\therefore d\mid (a-kb)$$
$$\therefore d\mid r$$
因此$b,r$的公约数集合与$a,b$的公约数集合相等，显然它们的最大公因数也相等。
证毕。
然后我们看这题是问三个数的最大公因数。貌似和两个数的最大公因数没有什么关系，其实原理是一样的，三个数的最大公因数=两个数的最大公因数和第三个数的最大公因数，即
$$gcd(x,y,z)=gcd(x,gcd(y,z))$$
---------
然后，因为C++自带gcd，可以直接求解
代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
scanf("%d%d%d",&a,&b,&c);//输入
printf("%d",__gcd(a,__gcd(b,c)));//输出
}
```
最后再放一个辗转相除法的模板吧
```cpp
int gcd(int x,int y){return x%y?gcd(y,x%y):y;}
```
其实这行是一个三目运算符的应用，也可以转换为
```cpp
if(x%y==0) return y；
else return gcd(y,x%y)
```