P8636 [蓝桥杯 2016 省 AB] 最大比例【GCD】
P8636 [蓝桥杯 2016 省 AB] 最大比例
题目描述
X 星球的某个大奖赛设了M MM级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16 , 24 , 36 , 54 16,24,36,5416,24,36,54
其等比值为：3 / 2 3/23/2。
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式
第一行为数字N ( 0 < N < 100 ) N(0<N<100)N(0<N<100)，表示接下的一行包含N NN个正整数。
第二行N NN个正整数X i ( X i < 10 12 ) X_i(X_i<10^{12})Xi(Xi<1012)，用空格分开。每个整数表示调查到的某人的奖金数额。
输出格式
一个形如A / B A/BA/B的分数，要求A AA、B BB互质。表示可能的最大比例系数。
测试数据保证了输入格式正确，并且最大比例是存在的。
输入输出样例 #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 题）。
问题链接：P8636 [蓝桥杯 2016 省 AB] 最大比例
问题分析：数论问题，不解释。
参考链接：LQ0047 最大比例【GCD】
题记：（略）
AC的C++语言程序如下：
/* LQ0047 最大比例 */#include<iostream>#include<algorithm>#include<map>usingnamespacestd;typedeflonglongLL;constintN=100;LL b[N],c[N],a[N];LLgcd2(LL a,LL b){if(a<b)swap(a,b);if(b==1)returna;returngcd2(b,a/b);}intmain(){intn;while(cin>>n){for(inti=0;i<n;i++)cin>>a[i];sort(a,a+n);intcnt=0;for(inti=1;i<n;i++)if(a[i]!=a[i-1]){LL gcd=__gcd(a[i],a[i-1]);b[cnt]=a[i-1]/gcd;c[cnt++]=a[i]/gcd;}LL t1=b[0],t2=c[0];for(inti=1;i<cnt;i++){t1=gcd2(t1,b[i]);t2=gcd2(t2,c[i]);}cout<<t2<<"/"<<t1<<endl;}return0;}