10. 最大比例

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且,相邻的两个级别间的比例是个固定值。
也就是说:所有级别的奖金数构成了一个等比数列。比如:
16,24,36,54
其等比值为:3/2
现在,我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。

输入格式:
第一行为数字N(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

请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。 所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。 注意:
所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。

这题比较复杂,我们需要分析一下。
首先比值都是相邻级别的,所以我们可以将这n个数排序再去重,
(如果只剩一个数的话,那答案应该是无穷大,这里就不考虑了)
然后把相邻的比值都算出来,为了方便讨论,再进行排序去重。
得到一个序列,$f_0=q^{k_0}, f_1=q^{k_1}, \dots, f_{n-1}=q^{k_{n-1}}$,$k_i$ 严格递增。

如果我们真的知道$q$和这些整数$k$,那么答案就是$q^g$,其中$g$是所有$k$的最大公约数。
为什么呢?
因为我们要找的是一个$x$,使得 $\log_{q^x}f_i$ 均为整数,即$\frac{k_i}{x}\log_qq=\frac{k_i}{x}$均为整数,
显然$x$是所有$k$的约数,且$x$最大,所以所求的$x$就是$g$。

当然问题在于我们根本不知道$q$和这些$k$,但是我们很惊喜的看到了最大公约数。
这里我们可以借鉴辗转相减法的操作 辗转相减法资料
不妨取两个数,定义$Q(a,b)$是由$a,b$唯一确定的最大比例,
且$Q$定义在无序对上,即$Q(b,a)=Q(a,b)$。
那么$Q(a,b)=Q(q^x,q^y)=q^{gcd(x,y)}=Q(q^x,q^{y-x})=Q(a,\frac{b}{a})\quad a<b$
所以我们只需要重复这个“辗转相减法”就可以得到最后的答案。

具体实现的时候可以每次只操作相邻的两个比值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=110;
const ll MAX=1000000000000;
ll a[N];

ll gcd(ll a,ll b)
{
if (!b) return a;
return gcd(b,a%b);
}

struct Frac
{
ll up,dw;
Frac() {}
Frac(ll a,ll b) {
if (a==0) {
up=0;dw=1;
return;
}
ll g=gcd(a,b);
up=a/g;dw=b/g;
}
bool operator <(const Frac &b) const {
return up*b.dw<dw*b.up;
}
bool operator ==(const Frac &b) const {
return !((*this)<b)&&!(b<(*this));
}
Frac operator /(const Frac &b) {
return Frac(up*b.dw,dw*b.up);
}
void print() {
printf("%I64d/%I64d\n",up,dw);
}
} f[N];

int main()
{
int n;
scanf("%d",&n);
for (int i=0;i<n;i++) {
scanf("%I64d",&a[i]);
}
sort(a,a+n);
n=unique(a,a+n)-a-1;
for (int i=0;i<n;i++) {
f[i]=Frac(a[i+1],a[i]);
}
Frac ans(MAX,1);
while (n>1) {
sort(f,f+n);
if (f[0]<ans) ans=f[0];
n=unique(f,f+n)-f-1;
for (int i=0;i<n;i++) {
f[i]=f[i+1]/f[i];
}
}
if (f[0]<ans) ans=f[0];
ans.print();
return 0;
}