最大比例
题意
给出一个等比数列中的几项，求出符合这几项的最大等比值。
思路
这几项排序、去重之后，按照通项公式写出来，第i个数 ：第一个数 = r^k。 其中r为一个比例，其gcd（分子，分母）= 1.。那么构成一个新数列，这个数列为：（p/q）k1 , (p/q)k2 ,(p/1)k3… 转化为：求这个新数列的最大公约数，因为有指数的形式，采用 更相减损术求这些指数的最大公约数。
代码
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
#define mst(s,_s) memset(s, _s, sizeof(s))
const double PI
= acos(-1.0);
const double eps
= 1e-6;
const int INF
= 0x3f3f3f3f;
const int N
= 1e6+100;
int T
,n
,m
;
ll a
[N
],_a
[N
];
int cnt
;
ll
gcd(ll a
,ll b
)
{
return !b
?a
:gcd(b
,a
%b
);
}
ll up
[N
],down
[N
];
ll
_gcd(ll a
,ll b
)
{
if(a
<b
) swap(a
,b
);
if(b
==1 ) return a
;
return _gcd(b
,a
/b
);
}
int main() {
cin
>>n
;
for(int i
=0;i
<n
;i
++) cin
>>a
[i
];
sort(a
,a
+n
);
for(int i
=0;i
<n
;i
++)
{
int j
=i
;
while(a
[i
]==a
[j
])
{
j
++;
}
_a
[cnt
++]=a
[i
];
i
=j
-1;
}
n
=cnt
;
for(int i
=1;i
<n
;i
++)
{
ll d
=gcd(_a
[0],_a
[i
]);
up
[i
]=_a
[i
]/d
;
down
[i
]=_a
[0]/d
;
}
ll _up
=up
[1],_down
=down
[1];
for(int i
=1;i
<n
;i
++)
{
_up
=_gcd(up
[i
],_up
);
_down
=_gcd(down
[i
],_down
);
}
cout
<<_up
<<"/"<<_down
<<endl
;
return 0;
}```
