蓝桥杯算法题：最大比例

题目描述：
X星球的某个大奖赛设了 M 级奖励。

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

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

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

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

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

请你据此推算可能的最大的等比值。

输入格式：
第一行为数字 N ，表示接下的一行包含 N 个正整数。

第二行 N 个正整数 Xi，用空格分开，每个整数表示调查到的某人的奖金数额。

输出格式：
一个形如 A/B 的分数，要求 A、B 互质，表示可能的最大比例系数。

数据范围：
0<N<100
0<Xi<10^9
数据保证一定有解。

输入样例1：
3
1250 200 32
输出样例1：
25/4

这道题，做的时候可以气死我，为什么呢？首先我觉得它的范围有问题，就是这里的Xi它说小于10的九次方，所以用int也不会超的吧，没想到他还真超了呢，我看了很多遍代码，都没看见什么乘法和加法能让一个数超int的，然后我去看别人的博客，发现，XX的，别的博客给的Xi范围是10^12，不会蓝桥云课刷题那里写少了吧，气死我了，我真的真的改了很久的代码！！！！！

然后第二个气人的点是，这道题没卡测试点，所以直接用gcd求出相邻两数的互质比值，找出整个范围最小的那个就可以了，这样好像也可以过，不过怎么会这样子，比如说三个奖励1 4 32，最大合适的比例应该是2/1，而不是4/1，我看见有个人的代码，结果是4/1也能对，就是好像蓝桥云课刷题那里拿的测试点太低端了，卡不了代码，气死我了！！！！！测试点都不好好弄一下

接下来说思路：要想找到最小比例，得用指数的更相减损术，可以看一下另一个博客：

http://t.csdnimg.cn/NPZtY

有了这个，代码就好写了，哦对，记得审题，题目可能有重复的奖金，因为有不同的人可能拿同一类奖金，这个要筛掉，不然会出问题的！！！！

ac代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
#define ll long long
ll x[N],temp[N];
ll a,b;
ll gcd_sub(ll x1,ll x2) { if(x1<x2)swap(x1,x2);//保证x1比x2大 if(x2==1)return x1;return gcd_sub(x2,x1/x2); 
}
int main() {int n;cin>>n;for(int i=0; i<n; i++)cin>>temp[i];int len=0;sort(temp,temp+n);x[len++]=temp[0];for(int i=1;i<n;i++){if(temp[i]!=temp[i-1])x[len++]=temp[i];}if(len==1) {printf("%ld/1",x[0]);} else {a=x[1]/__gcd(x[0],x[1]),b=x[0]/__gcd(x[0],x[1]);for(int i=2; i<len; i++) {ll d=__gcd(x[i],x[i-1]);a=gcd_sub(a,x[i]/d);b=gcd_sub(b,x[i-1]/d);}printf("%ld/%ld",a,b);}return 0;
}