题解：P8636 [蓝桥杯 2016 省 AB] 最大比例

· · 题解

题目传送门：P8636 [蓝桥杯 2016 省 AB] 最大比例

很久没有关注过洛谷了，洛谷发生了翻天覆地的变化，然鹅社区贡献也掉了一堆，于是前来补题解。

前置知识

题意简述

给定一个等比数列中的几项（可能乱序，可能重复），求这个等比数列的最大比值。

解题思路

因为可能是乱序的，所以先排个序，然后取个重，这步很好理解。

然后计算出每两项之间比值分子分母的最大公约数。

最后对两个处理过后的分子分母的序列求一次幂的最大公约数就可以过掉啦！

时刻谨记：十年 OI 一场空，不开 long long 见祖宗。

完整代码

看完上面再看这儿，不能只看这儿，更不能 Copy！

#include <algorithm>
#include <cstdio>

typedef long long int ll;
constexpr int N = 105;
ll n, x, y, a[N], b[N], c[N]; // 数列、分子、分母

ll gs(ll a, ll b) // 所谓的 gcd^2（划掉）
{
    if (a < b) std::swap(a, b);
    if (b <= 1) return a;
    return gs(b, a / b);
}

int main(void)
{
    scanf("%lld", &n);

    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    std::sort(a + 1, a + 1 + n); // 排序
    n = std::unique(a + 1, a + 1 + n) - a; // 去重

    for (int i = 2; i <= n; i++) // 处理分子分母
    {
        b[i] = a[i] / std::__gcd(a[i], a[i - 1]);
        c[i] = a[i - 1] / std::__gcd(a[i], a[i - 1]);
    }

    x = b[1];
    y = c[1];

    for (int i = 2; i <= n; i++) // 处理最终答案
    {
        x = gs(x, b[i]);
        y = gs(y, c[i]);
    }

    printf("%lld/%lld", x, y);

    #define _ 0
    return ~~(0^_^0);
    #undef _
}

这是本五年级蒟蒻小学生的第 26 篇题解，不喜可喷，但求你不要喷太猛了哦~

更新日志