题目描述

X星球的某个大奖赛设了 M 级奖励。

每个级别的奖金是一个正整数。

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

也就是说：所有级别的奖金数构成了一个等比数列。

比如：16,24,36,54，其等比值为：3/2。

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

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

输入格式
第一行为数字 N ，表示接下的一行包含 N 个正整数。

第二行 N 个正整数 Xi，用空格分开，每个整数表示调查到的某人的奖金数额。

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

数据范围
0<N<100
0<Xi<1012
数据保证一定有解。

样例

输入样例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

思路
我们要找一个数列的最大的等比值。
这种感觉和等差数列很相似，我们直接往GCD上靠

由于一串数据，排序之后肯定存在等差q

s= s1, s2 , s3 …sq … sn
s= aq^0,aq^1, aq^2 …a^q^k....aq^n

每个位次上都可以转换为[p/q]^w形式，即si=[s/a0,s/ai]^k
存在公比形如[p/q]^k
因为[p/q]^k>0,要使得整体最大则公比系数最大，则求K最大

k的限制条件
[p/q]^w是[p/q]^k的次幂
[p/q]^w=（[p/q]^k）^s=[p/q]^k^s
则k是每一个w的约数
k最大就是wi的最大公约数

状如[p/q]^wi
我们现在转向了求每一个wi的最大公约数

[p/q]^k = [p^k/q^k]
我们可以直接求取分子分母
则分别求分子分母指数最大公约数

辗转相减法

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
long long a[105];
//辗转相除法
long long gcd(long long a,long long b){
 if(b==0) return a;
 else return gcd(b,a%b);
}
//辗转相减法
long long gcd_sub(long long a,long long b){
 if(a<b) swap(a,b);
 if(b==1) return a;//指数是0，b是1 
 else return  gcd_sub(b,a/b);
}
int main(int argc, char** argv) {
 scanf("%d",&n);
 for(int i=0;i<n;i++){
  scanf("%lld",&a[i]);
 }
 sort(a,a+n);
 long long dd;
 long long fm[105];
 long long fz[105];
 int cnt=0;
 for(int i=1;i<n;i++){
  if(a[i]!=a[i-1]){
   long long dd=gcd(a[i],a[0]);
   fz[cnt]=a[i]/dd;
   fm[cnt]=a[0]/dd;
   cnt++;
  }
 }
 //分别求分母分子的最大公约数
 long long up=fz[0],down=fm[0]; 
 for(int i=1;i<cnt;i++){
  up=gcd_sub(up,fz[i]);
  down=gcd_sub(down,fm[i]);
 }
 printf("%lld/%lld\n",up,down);
 return 0;
}