题解 | 最大公约数1（附带欧几里得原理解释+代码细节）

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int main()
{
    int n;
    while(cin>>n)
   { 
    vector<int>a(n);
   for(int i=0;i<n;i++)
    {
        
       cin>>a[i];
    }
    sort(a.begin(),a.end());
    int k=gcd(a[n-1],a[0]);
    cout<<a[0]<<" "<<a[n-1]<<" "<<k;
    cout<<'\n';
   }
    return 0;
}

这一题我们要用到gcd函数，这函数在一些版本里可以直接引用

以下是我知道的两种直接引用方式：

int k=_gcd(a,b);

int k=gcd(a,b);

本题中我们直接模拟了

int gcd(int a,int b)

{

if(a%b==0) return b;

return gcd(b,a%b);

}

方法原理：

数学基础：欧几里得算法，它是求最大公约数的经典算法。

a模b有余数时我们用较小的数模上它的余数直到余数为零，此时的b就是我们要找的最大公约数。

对应数学解释：

设d为最大公约数，则d可以整除a也可以整除b，余数r=(a-b*k)(b为较小的数)//这里我们回忆一下结论：以余数为新b，b为新a，找到的最终余数为零时即b=0得到新a为最终答案。当找到那个a%r(新)==0的情况r就是答案//存在m,n使得a=d*m,b=d*n;

r=(d*m-d*n*k)=d(m-nk);d时b和r的公约数//利用这个性质，我们可以反复更新a,b//因为r严格小于b，所以数组严格递减，一定有r=0的情况，那我们找的b就是最大公约数

可能出现问题：

没有考虑多组数据情况，while(cin>>n)；

细节vector<int>a(n)//用小括号初始化数组，并且可以动态初始化数组大小。

gcd中a,b大小顺序。