题目描述

题目抽象成 给定等比数列的某些项，求可能的最大的公比。

容易想到的是 先对数据 排序， 去重；
然后 1. 每一项除以第一项
2. 每一项除以前一项

来得到只含有 q^k (q为最大公比，k为整数) 的整数序列。

其中 q = A / B , A、B满足没有公因子，且分式不可再写成 某一分式的 k 次方的形式。
第一个要求是题目要求的，直接分子分母同除最大公约数即可。
第二个要求也可以到达， 需要对分子分母 分别 分解质因子，对每个质因子的 次方 求最大公约数。
结果就是 分子分母 分别是 自身 每个 质因子 该次方 的乘积。

对于题目要求的最大公比 q^k (注意这里的q和上文概念不同，这里q^k表示最大公比) ，一定可以写成 q^k^s = q^d[i]的形式， 其中d[i]的定义在下图中给出了。
所以对于每一个d[i]，k一定是 d[i] 的 因子。
故 k 是所有 d[i] 的最大公因子。
因此 q^k 可求。

注意：这里求最大公因子要用辗转相减法，而不用辗转相除法。
因为 k 是指数，对指数取余后， 整个数的真值比较难维护。
而且题干中数据只有 1e12 ，指数最大是 40+ ，时间复杂度是没有问题的。

![_9NL5E_JD]NU)0LVFL8ZEL.png](https://cdn.acwing.com/media/article/image/2021/04/10/28491_7c674ed899-_9NL5E_JD]NU)0LVFL8ZEL.png)

C++ 代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=110;

int n;
LL a[N],b[N],x[N];

LL gcd(LL a,LL b)
{
    return b ? gcd(b,a%b) : a;
}

LL gcd_sub(LL a,LL b)
{
    if(a<b) swap(a,b);
    if(b==1) return a;
    return gcd_sub(b,a/b);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>x[i];

    sort(x,x+n);
    int cnt=0;
    for(int i=1;i<n;i++)
    {
        if(x[i]!=x[i-1])
        {
            LL d=gcd(x[i],x[0]);
            a[cnt]=x[i]/d;
            b[cnt]=x[0]/d;
            cnt++;
        }
    }

    LL up=a[0],down=b[0];
    for(int i=1;i<cnt;i++)
    {
        up = gcd_sub(up,a[i]);
        down = gcd_sub(down,b[i]);
    }

    cout<< up <<'/' <<down<<endl;

    return 0;
}