最大比例公约数复用【蓝桥真题】（c++）

最大比例

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

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

输入格式：
第一行为数字N（1<N<100），表示接下的一行包含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

我的思路

本题解析：所有奖金数构成一个等比数列，那么随机选取的某部分奖金数之间满足()^k^的关系，q为公比，k为平方数。
思路说明：

选取的部分奖金先排序，然后将部分奖金数中所有相邻两个数A、B（A>B）两两分组，并计算对应的商 S = A/B = ()^k^。
求得k,并将()^k^代入计算，若不存在所有的S均能由(()^k^)^n^表示，则更新k（利用公约数的更新方式）
最后输出 S ，即为该算法的答案。

公约数更新方式说明：求得的每对A/B = Si，i = 1 - (N-1),比如S1 = 625/16,S2 = 125/8，他们的最大比例这样求，625/16 = （5/2）^4^，125/8 = （5/2）^3^，所以他们的最大比例等于4、3的最大公约数，即（5/2）^1^。

算法展示

个人实现（答案有误）

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long LL;

LL N,in[101];//选取奖金总数

LL mons[101],A,B,cnt;//mons:随机选取的奖金数，A:除数，B:被除数,cnt:辅助变量。

struct Gc{

    LL A,B;

    Gc(LL _A,LL _B):A(_A),B(_B)//约分

    {

        LL _gcd = maxDiv(A,B);//求最大公约数

        A/=_gcd;

        B/=_gcd;

    }

    LL maxDiv(LL A,LL B)//最大公约数求解

    {

        if(B==0)return A;

        return maxDiv(B,A%B);

    }

};

vector<Gc> gcs;

//求最大公约数

LL comDiv(LL a,LL b)//q对应的不同比率之间的最大公约数

{

    if(b==0) return a;

    return comDiv(b,a%b);

} 

//求公比平方数

LL  powcnt(LL a)

{

    for(LL i =40;i>0;i--)//求得公约数

    {

        if(pow(gcs[0].A,1.0/i)!=-1)return i;

    }

    return -1;

}

int main() {

    //输入规模

    cin>>N;

    for(LL i = 0;i< N;i++)

    {

        cin>>in[i];

    }

    //升序排序

    sort(in,in+N);

    if(N==2)

    {

        cout<<in[1]<<"/"<<in[0]<<endl;

        return 0;

    }

    // 存入vector

    for(LL i=0;i<N-1;i++)

    {

        if(in[i]!=in[i+1])gcs.push_back(Gc(in[i+1],in[i])); //添加每组数据

    }

    //利用A,B最大公约数k求解

    LL div = powcnt(gcs[0].A);

    A = pow(gcs[0].A,1.0/div),B =pow(gcs[0].B,1.0/div);//记录最小数 

    for(LL j= 0;j<gcs.size();j++)//比较公比平方数

    {

        LL cnt = powcnt(gcs[j].A);

        LL com = comDiv(div,cnt);

        if(div>com)div = com;

        if(div==1)break;

    } 

    cout<<pow(A,div)<<"/"<<pow(B,div)<<endl;

    return 0;

}

网上借鉴：https://blog.csdn.net/lbperfe...

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<stack>

#include<vector>

#include<cmath>

#define MAX 100005

typedef long long ll;

using namespace std;

ll a[105];

struct node

{

    ll x,y;

}p[105];

bool cmp(node xx,node yy)

{

    return xx.x<yy.x;

}

int main()

{

    int n;

    cin>>n;

    for(int t=0;t<n;t++)

    {

        scanf("%lld",&a[t]);

    }

    sort(a,a+n);

    ll s1;

    ll x,y;

    int cnt=0;

    for(int t=n-1;t>=1;t--)

    {

        if(a[t]!=a[t-1])

        {

           s1=__gcd(a[t],a[t-1]);

           p[cnt].x=a[t]/s1;

           p[cnt++].y=a[t-1]/s1;

        }

    }

    sort(p,p+cnt,cmp);

    ll minn=p[0].x;

    x=p[0].x;

    y=p[0].y;

    for(int t=0;t<cnt-1;t++)

    {

        if((p[t+1].x/p[t].x)<minn&&p[t+1].x/p[t].x!=1)

        {

            x=p[t+1].x/p[t].x;

            y=p[t+1].y/p[t].y;

        }

    }

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

    return 0;

}

上文链接：交换瓶子标记+归位【蓝桥真题】（c++）

巴特西

最大比例公约数复用【蓝桥真题】（c++）

最大比例

我的思路

算法展示

最新文章

热门文章

巴特西

最大比例 公约数复用 【蓝桥真题】 （c++）

最大比例

我的思路

算法展示

最新文章

热门文章

最大比例公约数复用【蓝桥真题】（c++）