题目描述
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
C++ 代码
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=110;
int n;
ll x[N],a[N],b[N];//存原数,分子,分母
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
//求公比的各指数的最大公约数,求最大公约数可用更相减损法
ll gcd_sub(ll a,ll b){//因为数据范围(40左右)较小,所以可以用更相减损法
if(a<b)swap(a,b);
if(b==1)return a;
return gcd_sub(b,a/b);
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>x[i];
sort(x,x+n);//排序
int cnt=0;
for(int i=1;i<n;i++)//去重
if(x[i]!=x[i-1])
{
ll d=gcd(x[i],x[0]);
a[cnt]=x[i]/d;//分子
b[cnt]=x[0]/d;//分母
cnt++;
}
ll up=a[0],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;
}