X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且,相邻的两个级别间的比例是个固定值。
也就是说:所有级别的奖金数构成了一个等比数列。比如:
16,24,36,54
其等比值为:3/2
现在,我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式:
第一行为数字 N (0<N<100),表示接下
的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000),用空格分开。每个整数表示调查到的某人的奖金数额
要求输出:
一个形如A/B的分数,要求A、B互质。表示可能的最大比例系数
测试数据保证了输入格式正确,并且最大比例是存在的。
例如,输入:
3
1250 200 32
程序应该输出:
25/4
再例如,输入:
4
3125 32 32 200
程序应该输出:
5/2
再例如,输入:
3
549755813888 524288 2
程序应该输出:
4/1
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 3000ms
假设比例为q,则我们对数据降序排序后不停的使用前一个除去后一个会得到一个商,也就是q的n次方,再求出所有得到的商的最大公约数,即q即可,但问题在于本题的商不一定是整数于是使用分数的做法,使用辗转相除
当然,我也不能确定我的是否正确,如有错误,希望指正
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long int cmp(long long int a,long long int b)
{
return a>b;
}
int main()
{
double s=9999999999;//最小的公约数
int mia,mib;//存最小的公约数分数形式
long long int a[1500];
int N;
cin>>N;
for(int i=0;i<N;i++)
{
scanf("%lld",&a[i]);
}
sort(a,a+N,cmp);
int x=1,y=1;
int t=0;
for(int i=0;i<N-1;i++)
{
if(a[i]==a[i+1])//去重
continue;
int n=a[i],m=a[i+1];
int c;
while(1)//先求i和i+1个数的商,用分数表示
{
c=n%m;
n=m;
m=c;
if(c==0)
break;
}
if(t==0)//表示这是第一个商
{
t=1;
x=a[i]/n,y=a[i+1]/n;
mia=x,mib=y;
s=1.0*x/y;
}
else
{
x=a[i]/n,y=a[i+1]/n;//分数形式的商
while(1)
{
if(s==1.0*x/y)//找到第i个商和前i-1个商的最大公约数
break;
else if(s>1.0*x/y)
{
int h=x,g=y;
x=mib*x,y=mia*y;
n=x,m=y,c;
while(1)
{
c=n%m;
n=m;
m=c;
if(c==0)
break;
}
x=x/n,y=y/n;
if(x<y)
c=x,x=y,y=c;
s=1.0*h/g;//保证s存的是最小的那一个
mia=h,mib=g;
}
else if(s<1.0*x/y)
{
x=mib*x,y=mia*y;
n=x,m=y,c;
while(1)
{
c=n%m;
n=m;
m=c;
if(c==0)
break;
}
x=x/n,y=y/n;
if(x<y)
c=x,x=y,y=c;
}
}
}
}
printf("%d/%d",x,y);
}