最大比例（蓝桥杯C/C++2016B组省赛）

[蓝桥杯 2016 省 AB] 最大比例

题目描述

X 星球的某个大奖赛设了 $M$ 级奖励。每个级别的奖金是一个正整数。

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

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

$16,24,36,54$

其等比值为：$3/2$。

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

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

输入格式

第一行为数字 $N(0<N<100)$，表示接下的一行包含 $N$ 个正整数。

第二行 $N$ 个正整数 $X_i(X_i<10^{12})$，用空格分开。每个整数表示调查到的某人的奖金数额。

输出格式

一个形如 $A/B$ 的分数，要求 $A$,$B$ 互质。表示可能的最大比例系数。

测试数据保证了输入格式正确，并且最大比例是存在的。

样例 #1

样例输入 #1

3
1250 200 32

样例输出 #1

25/4

样例 #2

样例输入 #2

4
3125 32 32 200

样例输出 #2

5/2

样例 #3

样例输入 #3

3
549755813888 524288 2

样例输出 #3

4/1

提示

时限 3 秒, 256M。蓝桥杯 2016 年第七届省赛

蓝桥杯 2016 年省赛 A 组 J 题（B 组 J 题）。

题解

我的代码

不知道怎么写出来的... 76

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

using ll = long long;

int main() {
    int n;
    scanf("%d", &n);
    vector<ll> arr;
    set<ll> tmp_set;
    for (int i = 0; i < n; ++i) {
        ll j;
        scanf("%lld", &j);
        tmp_set.insert(j); 
    }
    
    for (ll it : tmp_set) {
        arr.push_back(it); 
    }
    
    // 16 -1.5 (*3 / 2)-> -1.5 (*3 / 2)--> 36 -1.5 (*3 / 2)--> 54
    // a b c
    // b = q*a, c = p*b
    // 公比 = p, q 的 最小公约数
    // p = 36 / 16 = 3
    // q = 54 / 36 = 1.5
    
    double q = 1e18; 
    // 32 ->*6-> 200 ->15-> 3125  15/6 -> 5/2
    // 2 ->*262,144-> 524288 -> *1,048,576 -> 549755813888 1,048,576/262,144 = 4/1  
    double p = 0; 
    for (int i = 1; i < arr.size(); ++i) {
        double tmp = (double)arr[i] / arr[i - 1];
        q = min(q, tmp);
        p = max(p, tmp);
    }
    
    double res = p / q;
    if (res == 1.0) {
        ll gy = __gcd(arr[1], arr[0]);
        printf("%lld/%lld\n", arr[1] / gy, arr[0] / gy);
    }
    else {
        ll fm = 1, fz;
        while (res - (ll)res >= 1e-6) {
            res *= 10;
            fm *= 10;
        }
        fz = res;
        ll gy = __gcd(fz, fm);
        if (fz / gy)
            printf("%lld/%lld\n", fz / gy, fm / gy);
        else
            printf("0/0\n");
    }    
    
    
    /*
2 -> *262,144-> 524288 -> *1,048,576 -> 549755813888 *2 -> x

1,048,576/262,144 = 4/1

4
16 24 36 54

3
16 36 54

6
2 32 8 16 32 128
    */
    
    return 0;
}

C++