—— Summon, Light!
0%

2016年蓝桥杯省赛C/C++ A组 最大比例

发表于 更新于 Valine：

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;
}
咖啡，亦我所需也