题目:最大比例
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且,相邻的两个级别间的比例是个固定值。
也就是说:所有级别的奖金数构成了一个等比数列。比如:
16,24,36,54
其等比值为:3/2
现在,我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式:
第一行为数字N,表示接下的一行包含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
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
解题思路:这一题,我先对n个数排序,然后相邻两个相除,得到n-1个数,这n-1个数都是公比的正整数次方,然后我把两个次方数在相除,都是大的除小的,打个比方,两个数位q^15和q^6,
q^15/q^6 = q^9, q^9/q^6 = q^3 , q^6/q^3 = q^3 q^3/q^3 = 1,不然它等于1,所以保留q^3,说明两个是都是q^3的次方,
然后也是连续两个数按上面方法处理,每一次从头到尾处理过后,n-1个数变为n-2个数,n-2个数变为n-3个,....直到只剩一个数就是答案,这个数不一定是q,可能是q的m次方,如果是q的m次方,说明输入的数都是这个数的次方,那这个数就可以当作这个数列的公比,当然q也可以作为这个数列的公比,甚至q,q^2,....q^m次方都可以作为公比,按题意输出最大的,就是剩下来的数。
要严谨的数学证明的话,不会,只是觉得两个不同次方,一直大的除小的,就是次方相减,最后可以得到一个数,就好像最大公约数一样。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
struct Node{
LL x, y;
};
LL arr[105];
vector<Node> vec;
LL gcd(LL a, LL b){
if(a%b == 0)return b;
return gcd(b, a%b);
}
void getAns(){
vector<Node> tmp = vec;
vec.clear();
Node head = tmp.at(0);
LL xa = head.x, ya = head.y;
for(int i=1; i<tmp.size(); ++i){
LL xb = tmp.at(i).x, yb = tmp.at(i).y;
while(xa!=xb || ya!=yb){
if(xa*yb<ya*xb){
swap(xa, xb);
swap(ya, yb);
}
// printf("%lld %lld %lld %lld\n", xa, ya, xb, yb);
LL xayb = xa*yb, xbya = xb*ya;
LL g = gcd(xayb, xbya);
xa = xayb/g;
ya = xbya/g;
}
Node node;
node.x = xa; node.y = ya;
vec.push_back(node);
}
}
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; ++i){
scanf("%lld", &arr[i]);
}
sort(arr, arr+n);
for(int i=0; i<n-1; ++i){
if(arr[i] == arr[i+1])continue;
LL g = gcd(arr[i+1], arr[i]);
Node tmp;
tmp.x = arr[i+1]/g; tmp.y = arr[i]/g;
vec.push_back(tmp);
}
if(vec.empty()){ //vec为空,这说明输入的数都一样
printf("1/1");
return 0;
}
while(vec.size() > 1){
// cout << vec.size() << endl;
getAns();
}
printf("%lld/%lld", vec.at(0).x, vec.at(0).y);
return 0;
}