2016年第七届蓝桥杯省赛-J. 最大比例

原题链接

题面

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

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

也就是说：所有级别的奖金数构成了一个等比数列。比如：16,24,36,54，其等比值为：$\frac{3}{2}$

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

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

输入描述

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

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

输出描述

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

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

输入样例 1

3
1250 200 32

输出样例 1

25/4

输入样例 2

4
3125 32 32 200

输出样例 2

5/2

输入样例 3

3
549755813888 524288 2

输出样例 3

4/1

题解

最大公因数，数论

先将读入的数组进行排序去重，再进行处理。

记 nums[0] 为首项，则当 $i > 0$ ，有 下式子：

$nums[i] = nums[0] \times q^{k_i} = nums[0] \times \frac{q_1^{k_i}}{q_2^{k_i}}$

其中 $q$ 为 最小公比，$k_i$ 为严格单调递增的整数。

题目要求 最大公比， 则可以转化为找到一个最大的 $x$， 使得 $(q^x)^{t_i} = q^{t_i\times x} = q^{k_i}$ （$t_i$ 为整数）成立，则可以知道，我们的目标即为找到满足 $x = gcd(k_1, k_2,\cdots,k_m)$ 的 $x$， 而 $q$ 表示为分数形式（$q = q_1/q_2$），则同理只要求出分子 $(q_1^x)^{t_i} = q_1^{t_i\times x} = q_1^{k_i}$ 的 $x$ ，即为分母的 $x$。

计算出每一个数 nums[i] ($i > 0$)与第一个数 nums[0] 的最简比例，记为 a[i]/b[i] ，有 $a[i]/b[i] = q_1^{k_i}/q_2^{k_i}$，再对分子 a 数组进行上述的求 $x$ 即可。

而对于一个 $\{q^{k_1}, q^{k_2},q^{k_3},\cdots ,q^{k_m}\}$ 这样的序列，要求其中 $\{k_1, k_2, k_3,\cdots,k_m\}$ 的最大公因数，则需用到 辗转相减法 的变形形式。

对于常规的求两个数 a 和 b 的最大公因数 $gcd(a, b)$，辗转相减法伪代码如下：

def gcd(a, b):
    if a < b: swap(a, b)
    if a == b: return a
    return gcd(b, a - b)

如求 12 和 15 的最大公因数如下计算：

则在本题中，我们求 $q^{k_1}$ 和 $q^{k_2}$ 的幂的最大公因数，则将两数相除，就能实现减法，即 $q^{k_1}/q^{k_2} = q^{k_1 - k_2}$，这样即可求的答案 $q^{gcd(k_1, k_2)}$，其伪代码如下：

# 传入的参数为 a(q^k1) 和 b(q^k2)，返回 q^gcd(k1, k2)
def gcd_sub(a, b):
    if a < b: swap(a, b)
    if a == b: return a
    return gcd(b, a / b)

具体实现过程见代码。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 105;
int n;
LL a[N], b[N];
vector<LL> nums;

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

//辗转相减法，变形---
//   对 a 和 b 的表示法 x^i 和 x^j 的幂 i j 进行取最大公因数，返回 x^gcd(i, j)
LL gcd_sub(LL a, LL b) {
    if (a < b) swap(a, b);
    if (b == 1) return a;
    return gcd_sub(b, a / b);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        nums.push_back(x);
    }

    //排序并去重
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    n = nums.size();
    for (int i = 1; i < n; i++) {
        LL g = gcd(nums[i], nums[0]);
        a[i] = nums[i] / g;
        b[i] = nums[0] / g;
    }

    LL fz = a[1], fm = b[1];
    for (int i = 2; i < n; i++) {
        fz = gcd_sub(a[i], fz);
        fm = gcd_sub(b[i], fm);
    }
    printf("%lld/%lld\n", fz, fm);

    return 0;
}