等比数列蓝桥 求最大比值

X星球的某个大奖赛设了 M

级奖励。

每个级别的奖金是一个正整数。

并且，相邻的两个级别间的比例是个固定值。

也就是说：所有级别的奖金数构成了一个等比数列。

比如：16,24,36,54
，其等比值为：3/2

。

现在，我们随机调查了一些获奖者的奖金数。

请你据此推算可能的最大的等比值。
输入格式

第一行为数字 N
，表示接下的一行包含 N

个正整数。

第二行 N
个正整数 Xi

，用空格分开，每个整数表示调查到的某人的奖金数额。
输出格式

一个形如 A/B
的分数，要求 A、B

互质，表示可能的最大比例系数。
数据范围

0<N<100

0<Xi<1012

数据保证一定有解。
输入样例1：

3
1250 200 32

输出样例1：

25/4

输入样例2：

4
3125 32 32 200

输出样例2：

5/2

输入样例3：

3
549755813888 524288 2

输出样例3：

4/1

这道题用到了辗转相减法，低配版辗转相除法
复杂度 o(n)

#include<bits/stdc++.h>
using namespace std;
long long x[110];
long long a[110],b[110]; long long gcd(long long a,long long b)
{
   
    return b?gcd(b,a%b):a;
}
long long gcd_sub(long long a,long long b)
{
   
    if(a<b) swap(a,b);//一定要保证a大于b，以为a要除以b
    if(b==a)    return a;
    gcd_sub(b,a/b);
}

int main()
{
   
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>x[i];
    sort(x,x+n);
    long long d=x[0];
    int cnt=0;
    for(int i=1;i<n;i++)
    {
   
        if(x[i]!=x[i-1])//只计算不同项
        {
   
        d=gcd(x[0],x[i]);
        a[cnt]=x[i]/d;//通分
        b[cnt]=x[0]/d;
        cnt++;}
    }
    long long up=a[0];
    long long down=b[0];
    for(int i=1;i<cnt;i++)
    {
   
        up=gcd_sub(up,a[i]);//只能用在指数倍上
        down=gcd_sub(down,b[i]);
    }
    cout<<up<<'/'<<down<<endl;
    return 0;
}