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

题目描述

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

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

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

$16, 24, 36, 54$

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

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

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

输入格式

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

第二行 $N$ 个正整数 $X_{i} (X_{i} < 1 0^{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 题）。

解析

解题思路：

这道题要求我们从给定的一部分奖金数额中，推算出可能的最大公比（即最大比例）。

基本分析： 由题意知，所有奖金构成一个等比数列，公比一定可以表示为最简分数 $A / B$ （因为各项均是正整数，且严格递增）。将我们抽样调查的数字去重并按升序排列，得到 $x_{1}, x_{2}, \dots, x_{k}$ 。因为它们是从同一个等比数列中抽取出来的，所以相邻两项的比值必然是公比 $A / B$ 的某个正整数次幂。即对于任意的 $i$ ，有： $\frac{x _{i + 1}}{x _{i}} = (\frac{A}{B})^{p_{i}} = \frac{A ^{p_{i}}}{B ^{p_{i}}}$
分子与分母分离： 因为 $g cd (A, B) = 1$ ，自然也就有 $g cd (A^{p_{i}}, B^{p_{i}}) = 1$ 。所以，如果我们将 $\frac{x _{i + 1}}{x _{i}}$ 约分到最简形式 $\frac{N _{i}}{D _{i}}$ ，我们就可以确切地得到： $N_{i} = A^{p_{i}}, D_{i} = B^{p_{i}}$
求最大的公比： 题目要求我们找到“最大的公比”，也就是说我们要让 $A / B$ 的值尽可能大。换个角度来看， $p_{i}$ 越小， $A / B$ 就越大。这就等价于我们要找到所有 $N_{i}$ 的“最大公共底数”作为 $A$ ，以及所有 $D_{i}$ 的“最大公共底数”作为 $B$ 。由于 $N_{i} = A^{p_{i}}$ ，我们实际上是要求所有 $p_{i}$ 的最大公约数 $g$ 对应的底数 $A^{g}$ 。这和欧几里得算法求最大公约数非常类似：对于两个同底数的幂 $X = A^{a}$ 和 $Y = A^{b}$ （假设 $X \geq Y$ ），它们的除法 $X / Y = A^{a - b}$ 正好对应了指数的减法。当不断进行相除并交换较小数时，直到两数相等，这本质上就是指数在进行“更相减损术”（或者说欧几里得算法）。
算法流程：
- 读入所有数字，去重并排序。
- 分别计算出相邻两项的最简分数比值，收集所有的分子 $N_{i}$ 放入列表，分母 $D_{i}$ 放入列表。
- 利用自定义的指数级别的最大公约数函数（不断让大数整除小数），求出所有分子的“最大公共底数” $A$ 和所有分母的“最大公共底数” $B$ 。
- 最终输出 $A / B$ 即可。

代码

//
// Created by 23264 on 2026/2/21.
//
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
ll GCD(ll a,ll b)
{
    while (b > 0)
    {
        ll temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
 
ll powerGCD(ll x,ll y)
{
    if (x == 0 || y == 0)
    {
        return 0;
    }
    while (true)
    {
        if (x == 1)
        {
            return y;
        }
        if (y == 1)
        {
            return x;
        }
        if (x < y)
        {
            swap(x,y);
        }
        x = x / y;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 0;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0;i < n;i++)
    {
        cin >> arr[i];
    }
    sort(arr.begin(),arr.end());
    arr.erase(unique(arr.begin(),arr.end()),arr.end());
    // 只有一个唯一元素时，公比直接是 1/1
    if (n <= 1) {
        cout << "1/1";
        return 0;
    }
 
    vector<ll> NList;
    vector<ll> DList;
 
    // 计算相邻项的比例，并化简为最简分数
    for (int i = 0;i < n - 1;i++)
    {
        ll num = arr[i + 1];
        ll den = arr[i];
        ll g = GCD(num,den);
        NList.push_back(num / g);
        DList.push_back(den / g);
    }
 
    // 对所有最简分数的分子求共同的“最大公共底数” A
    ll ansN = NList[0];
    for (int i = 1;i < NList.size();i++)
    {
        ansN = powerGCD(ansN,NList[i]);
    }
 
    // 对所有最简分数的分母求共同的“最大公共底数” B
    ll ansD = DList[0];
    for (int i = 1;i < DList.size();i++)
    {
        ansD = powerGCD(ansD,DList[i]);
    }
 
    cout << ansN << "/" << ansD;
}

枫禾(¬‿¬)

探索

P8636 最大比例