ACM-ICPC-OJ训练营

问题 2495 --最大比例(最大公约数+辗转相减法）

2495: 最大比例(最大公约数+辗转相减法）

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 1
[提交][状态][讨论版][命题人:]

题目描述

X星球的某个大奖赛设了 M 级奖励。

每个级别的奖金是一个正整数。

并且，相邻的两个级别间的比例是个固定值。

也就是说：所有级别的奖金数构成了一个等比数列。

比如：16,24,36,54，其等比值为：3/2。

现在，我们随机调查了一些获奖者的奖金数。

请你据此推算可能的最大的等比值。

输入描述

第一行为数字 N ，表示接下的一行包含 N 个正整数。

第二行 N 个正整数 Xi，用空格分开，每个整数表示调查到的某人的奖金数额。
0<N<100
0<Xi<1012
数据保证一定有解。

输出描述

一个形如 A/B 的分数，要求 A、B 互质，表示可能的最大比例系数。
(第七届蓝桥杯省赛C++A/B组)

样例输入

3
1250 200 32

样例输出

25/4

提示

我们要找一个数列的最大的等比值。

这种感觉和等差数列很相似，我们直接往GCD上靠

由于一串数据，排序之后肯定存在等差q

s= s1, s2 , s3 …sq … sn

s= aq^0,aq^1, aq^2 …a^q^k....aq^n

每个位次上都可以转换为[p/q]^w形式，即si=[s/a0,s/ai]^k

存在公比形如[p/q]^k

因为[p/q]^k>0,要使得整体最大则公比系数最大，则求K最大

k的限制条件

[p/q]^w是[p/q]^k的次幂

[p/q]^w=（[p/q]^k）^s=[p/q]^k^s

则k是每一个w的约数

k最大就是wi的最大公约数

状如[p/q]^wi

我们现在转向了求每一个wi的最大公约数

[p/q]^k = [p^k/q^k]

我们可以直接求取分子分母

则分别求分子分母指数最大公约数

来源

hichange

[提交][状态]