本文主要是介绍蓝桥杯-数论基础-最大比例，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
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
题解
我第一眼看见这个，就想到gcd和质因子，于是非常顺理成章的
1.打质数表（1e6），枚举质因子，对所有数都分解当前的质因子
2.对质因子幂次的变化取gcd
3.gcd就是质因子最小变化，即比例（q）
4.注意分清是分子还是分母
PS：我不知道超不超时，没有测试数据，就是单纯想记录一下思路（勿喷）
代码
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
const double eps=3e-8;
const ll mod=1e9;
const ll maxn=1000005;
int n,m;
vector<ll>prim;
bool noprim[maxn];
void init(){mem(noprim,0);noprim[1]=1;for(ll i=2;i<maxn;i++){if(!noprim[i])prim.push_back(i);for(int j=0;j<prim.size()&&1LL*prim[j]*i<maxn;j++){ll temp=prim[j]*i;noprim[temp]=1;if(i%prim[j]==0)break;}}
}
set<ll>a;
int main(){init();//打表while(scanf("%d",&n)){ll p,q,cnt,cn;//输入并去重a.clear();while(n--){scanf("%lld",&p);a.insert(p);}//分解质因子ll fenzi=1,fenmu=1;for(int i=0;i<prim.size();i++){p=prim[i];ll gcc=0;bool jia=false;cn=0;int cm=0;for(auto it:a){q=it;cnt=0;while(q%p==0){cnt++;q/=p;}if(cm!=0){if(cn<cnt){jia=true;}gcc=__gcd(gcc,abs(cnt-cn));//取质因子幂的gcd}cn=cnt;cm++;}if(jia){//if(i<10)printf("%lld:%lld\n",p,gcc);while(gcc--)fenzi*=p;}else {//if(i<10)printf("%lld:%lld\n",p,gcc);while(gcc--)fenmu*=p;}}ll sum=fenzi+fenmu,ans=max(fenzi,fenmu);cout<<ans<<"/"<<sum-ans<<endl;}return 0;
}
这篇关于蓝桥杯-数论基础-最大比例的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
