2016年蓝桥杯A组第十题最大比例

比赛时，当我看到这道题，我彻底的懵比了，没有思路，没有思路，没有思路，重要的事说三遍，赛后，也没有在网上找别人的代码看，因为对省赛感觉很不好，以为自己挂了，所以没有心情去看题，应该说是不敢去看题，成与败，关系着我的尊严，当初学校不让我报名A组，很多人都嘲讽我不知天高地厚，一个破二本的院校，还想挑战A组；更有人反问我，你才学了几天，到你比赛时撑死了也就学满七个月，就这么瞧不起B组？
实话说，我真的瞧不起B组，因为我相信自己的能力！

废话不多说，转入正题，对于这个题，我真的是没有一丝的思路可言，前天我百度了一下，网上还没有一个这道题相关的问题答案解析，没有办法，只能靠自己了，毕竟自己动手丰衣足食嘛。

先上题：

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2

现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。

输入格式：
第一行为数字N，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额

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

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

例如，输入：
3
1250 200 32

程序应该输出：
25/4

再例如，输入：
4
3125 32 32 200

程序应该输出：
5/2

再例如，输入：
3
549755813888 524288 2

程序应该输出：
4/1

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include ，不能通过工程设置而省略常用头文件。

苦于没有思路，苦于网上没有提示，只能自己想，最后，在一张废纸上找起了规律，结果发现真的毫无规律可言，只能作罢，用最朴素的办法解吧！

逆向思维考虑，需要求最大比例，那么肯定要从比例入手，所以首先就是求出所有的比例，并且去重，然后就需要对这些比例进行排序来谋求最大的基数，这个基数即为最大的比例。

思路听着很简单，但是实现起来着实麻烦，需要考虑的细节问题贼多，不多说了，看代码吧，代码更有说服力！

代码C：

#include <stdio.h>
#include <math.h>
#define _MAX 1000000000000

int N, p = 0;
long long M[100], nAtor[100], dAtor[100];
double W[100];

//M原数据排序去重
void sequenceM()
{
    int len = N, i , j;
    for (i = 0; i < N - 1; i++)
    {
        for (j = i + 1; j < N; j++)
        {
            if (M[i] > M[j])
            {
                M[i] ^= M[j];
                M[j] ^= M[i];
                M[i] ^= M[j];
            }
            else if (M[i] == M[j])
            {
                M[j] = _MAX;
                len--;
            }
        }
    }
    N = len;
// for (i = 0; i < N; i++)
// {
   
// printf("%lld ", M[i]);
// }
// printf("\n");
    return ;
}

//约分
void reduce(int i)
{
    long long j = M[i];
    for (; j > 0; j--)
    {
        if (M[i] % j == 0 && M[i + 1] % j == 0)
        {
            dAtor[i] = M[i] / j;
            nAtor[i] = M[i + 1] / j;
            return ;
        }
    }
    return ;
}

//W数据排序去重
void sequenceW()
{
    int len = N - 1, i , j;
    for (i = 0; i < N - 2; i++)
    {
        for (j = i + 1; j < N - 1; j++)
        {
            if (W[i] > W[j])
            {
                double tempW = W[i];
                W[i] = W[j];
                W[j] = tempW;
                long long tempN = nAtor[i];
                nAtor[i] = nAtor[j];
                nAtor[j] = tempN;
                long long tempD = dAtor[i];
                dAtor[i] = dAtor[j];
                dAtor[j] = tempD;
            }
            else if (W[i] == W[j])
            {
                W[j] = _MAX;
                len--;
            }
        }
    }
    N = len;
// for (i = 0; i < N; i++)
// {
   
// printf("%g %lld %lld\n", W[i], nAtor[i], dAtor[i]);
// }
    return ;
}

//分别求分子、分母基数
long long NDbase(long long *Ator)
{
    long long flag = Ator[0];
    if (N == 1)
    {
        return flag;
    }
    int i = 1, j, tag = 0;  //标记flag是否为符合基数要求
    for (; i < N; i++)
    {
        for (j = 2; pow((double)flag, (double)j) <= Ator[i]; j++)
        {
            if (pow((double)flag, (double)j) == Ator[i])
            {
                tag = 1;
                break;
            }
        }
        if (tag == 1)
        {
            tag = 0;
            continue;
        }
        break;
    }
    if (i == N)
    {
        return flag;
    }
    tag = 0;
    for (flag = Ator[0] / 2; flag > 0; flag--)
    {
        for (i = 0; i < N; i++)
        {
            for (j = 2; pow((double)flag, (double)j) <= Ator[i]; j++)
            {
                if (pow((double)flag, (double)j) == Ator[i])
                {
                    tag = 1;
                    break;
                }
            }
            if (tag == 1)
            {
                tag = 0;
                continue;
            }
            break;
        }
        if (i == N)
        {
            return flag;
        }
    }
    return 0;
}

//求最大基数
void base()
{
    long long N, D;   //最大比例的分子和分母
    N = NDbase(nAtor);
    D = NDbase(dAtor);
    printf("%lld/%lld\n", N, D);
    return ;
}
//求最大比例
void pro()
{
    int i;
    sequenceM();
    for (i = 0; i < N - 1; i++)
    {
        W[i] = M[i + 1] * 1.0 / M[i];
        reduce(i);
    }
    sequenceW();
    base();
    return ;
}

int main(int argc, const char * argv[])
{
    int i = 0;
    scanf("%d", &N);
    for (; i < N; i++)
    {
        scanf("%lld", &M[i]);
    }
    pro();
    return 0;
}