求 最大公约数 和 最小公倍数 的两种方法

输入格式（一定要看！！！！！！！！！！）

第一行为一个整数n，表示要求的数字的数量
第二行为要求最大公约数和最小公倍数的数字（共n个）

输出格式

第一行为这n个数的最大公约数
第二行为这n个数的最小公倍数

输入样例

3 
123 369 246

输出样例

123
738

• 1.死做

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N];
int n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    int Min=a[0],Max=a[0],Gcd,Lcm;
    for(int i=0;i<n;i++)Min=min(Min,a[i]);
    for(int i=Min;i>0;i--){
        bool key=true;
        for(int j=0;j<n;j++){
            if(a[j]%i!=0){
                key=false;break;
            }
        }
        if(key==true){
            Gcd=i;break;
        }
    }
    for(int i=0;i<n;i++)Max=max(Max,a[i]);
    for(int i=Max;i;i+=Max)
    {
        bool key=true;
        for(int j=0;j<n;j++){
            if(i%a[j]!=0){
                key=false;break;
            }
        }
        if(key){
            Lcm=i;break;
        }
    }
    printf("%d\n%d\n",Gcd,Lcm);
    return 0;
}

• 2.辗转相除法
  不知道的同学可以上网查，在这里不多做介绍，直接 上代码

#include<bits/stdc++.h>
using namespace std;
int n;
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int main(){
    scanf("%d",&n);
    int x;
    scanf("%d",&x);
    int Gcd=x,Lcm=x;
    for(int i=2;i<=n;i++){
        int x;
        scanf("%d",&x);
        Gcd=gcd(Gcd,x);
        Lcm=Lcm*x/gcd(Lcm,x);
    }
    printf("%d\n%d\n",Gcd,Lcm);
    return 0;
}

。。。