辗转相减法在求解最大等比值问题中的应用

在解决X星球的大奖赛奖金分配问题时，我们遇到了一个需要使用辗转相减法的场景。该问题要求根据已知的奖金数额推断出奖金级别之间可能的最大等比值。具体来说，X星球的大奖赛设置了M个级别的奖励，每个级别的奖金都是正整数，并且相邻级别的奖金比例保持一致，形成一个等比数列。

例如，一个可能的奖金序列是16, 24, 36, 54，其等比值为3/2。我们的任务是，根据随机调查的一些获奖者所获得的具体奖金数额，推算出这些奖金数额之间可能存在的最大等比值。

问题描述：

• 输入格式：
  
  
  
  • 第一行包含一个整数N，表示接下来一行将包含N个正整数。
  
  
  • 第二行包含N个正整数Xi，每个整数代表调查到的某位获奖者的奖金数额，各数值间以空格分隔。
  
  


• 输出格式：
  
  
  
  • 输出一个形如A/B的分数，其中A和B为互质的整数，表示可能的最大比例系数。
  
  


• 数据范围：
  
  
  
  • 0
    
  • 0
    
  • 数据保证至少存在一种解决方案。
  
  

示例：

输入样例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

算法实现：

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 115;
int n;
ll sniper[N], p[N], q[N];

// 计算最大公约数
ll gcd(ll a, ll b) {
    if (!b) return a;
    else return gcd(b, a % b);
}

// 使用辗转相减法计算最大公约数
ll gcd_sub(ll a, ll b) {
    if (a     if (b == 1) return a;
    else return gcd_sub(b, a / b);
}

int main() {
    int cnt = 0;
    cin >> n;
    for (int i = 0; i     sort(sniper, sniper + n);
    ll d;
    for (int i = 1; i         if (sniper[i] == sniper[i - 1]) continue;
        d = gcd(sniper[i], sniper[0]);
        q[cnt] = sniper[i] / d;
        p[cnt] = sniper[0] / d;
        cnt++;
    }
    ll res1 = q[0], res2 = p[0];
    for (int i = 1; i         res1 = gcd_sub(res1, q[i]);
        res2 = gcd_sub(res2, p[i]);
    }
    cout <    return 0;
}