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

mazhenhao0235 · 2025-02-16 12:13:22 · 题解

题目传送门

我们需要从给定的奖金数中找到一个等比数列的最大比例系数。

等比数列的特点是相邻两项的比例是固定的，且比例系数是一个分数 \frac{A}{B} ，其中A和B互质。

思路分析

1.首先将输入的奖金数排序并去重，因为等比数列中的数是有序的，且重复的数不会影响比例的计算。

2.对于排序后的序列，计算相邻两项的比例 \frac{x_i+1}{x_i} , 并将其化简为最简分数形式。

3.所有比例的最大公约数（GCD）就是可能的最大比例系数。

4.使用辗转相除法（欧几里得算法）计算分子和分母的最大公约数，将分数化简为最简形式。

展示代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>

using namespace std;

// 计算最大公约数（GCD）
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 化简分数
pair<long long, long long> red(long long a, long long b) {
    long long g = gcd(a, b);
    return {a / g, b / g};
}

// 计算比例的最大公约数
pair<long long, long long> sol(vector<long long>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    vector<pair<long long, long long>> r;
    for (size_t i = 1; i < v.size(); ++i) {
        long long a = v[i], b = v[i - 1];
        auto p = red(a, b);
        r.push_back(p);
    }

    // 计算所有比例的最大公约数
    long long A = r[0].first, B = r[0].second;
    for (size_t i = 1; i < r.size(); ++i) {
        A = gcd(A, r[i].first);
        B = gcd(B, r[i].second);
    }

    return red(A, B);
}

int main() {
    int N;
    cin >> N;
    vector<long long> v(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i];
    }

    auto res = sol(v);
    cout << res.first << "/" << res.second << endl;

    return 0;
}

这道题需通过排序、去重、计算比例并化简，最终找到最大比例系数。

本蒟蒻第一次写题解，求过QAQ