X星球的某个大奖赛设了 M 级奖励。
每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。
比如：16,24,36,54，其等比值为：3/2。
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式
第一行为数字 N ，表示接下的一行包含 N 个正整数。
第二行 N 个正整数 Xi，用空格分开，每个整数表示调查到的某人的奖金数额。
输出格式
一个形如 A/B 的分数，要求 A、B 互质，表示可能的最大比例系数。
数据范围
0
<
N
<
100
0
<
X
i
<
1
0
12
0<N<100\\ 0<Xi<10^{12}
0<N<1000<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
分析
此问题是关于等比数列求最大公比的问题。
首先，后一项除以前一项（每一项除以第一项）得到新数列{
q
α
1
,
q
α
2
,
q
α
3
.
.
.
q
α
n
q^{\alpha_1},\,q^{\alpha_2},\,q^{\alpha_3}\,...\,q^{\alpha_n}
qα1,qα2,qα3...qαn
由辗转相减法得到q
问题一：如何处理分式
采用两个数组分别存储分子和分母，分子分母同时除以两者的最大公因数即得到最简分数。
问题二：为什么要用辗转相减法
求
q
a
q^a
qa和
q
b
q^b
qb的最大公因数可以用辗转相除法但因为q是分数形式所以辗转相除法并不好用，这是采用辗转相减法就方便得多。
辗转相减法：
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
−
b
)
gcd(a, b)=gcd(b,a-b)
gcd(a,b)=gcd(b,a−b)
g
c
d
(
q
a
,
q
b
)
=
q
g
c
d
(
a
,
b
)
=
q
g
c
d
(
b
,
a
−
b
)
=
g
c
d
(
q
b
,
q
a
−
b
)
=
g
c
d
(
q
b
,
q
a
q
b
)
gcd(q^a, q^b)=q^{gcd(a,b)}=q^{gcd(b,a-b)}=gcd(q^b,q^{a-b})=gcd(q^b,\frac{q^a}{q^b})
gcd(qa,qb)=qgcd(a,b)=qgcd(b,a−b)=gcd(qb,qa−b)=gcd(qb,qbqa)
参考代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 110;
LL a[N];
LL p[N], q[N]; //p存分子，q存分母
int cnt;
int n;
LL gcd (LL a, LL b){
return b ? gcd(b, a % b) : a;
}
LL sub_gcd(LL a, LL b){
if(a < b) swap(a, b);
if(b == 1) return a;
else return sub_gcd(b, a / b);
}
int main (){
cin >> n;
for(int i = 0;i < n;i ++) cin >> a[i];
sort(a, a + n);
LL t;
//化简分式
for(int i = 1;i < n;i ++){
t = gcd(a[i], a[i - 1]);
p[cnt] = a[i] / t;
q[cnt] = a[i - 1] / t;
cnt ++;
}
//辗转相减法
LL res1, res2;
res1 = sub_gcd(p[0], p[1]), res2 = sub_gcd(q[0], q[1]);
for(int i = 2;i < cnt;i ++){
res1 = sub_gcd(res1, p[i]);
res2 = sub_gcd(res2, q[i]);
}
cout << res1 << "/" << res2 << endl;
return 0;
}
