这篇文章已经讲得非常完善了，主要是求最大公约数，辗转相减法这两个知识点

出处
作者：少年
链接：https://www.acwing.com/solution/content/22658/
来源：AcWing

#include<iostream>
#include<algorithm>

using namespace std;

const int N=110;

typedef long long LL;

LL x[N],a[N],b[N];
int cnt=0;

//假设原数列为 a,a*(p/q)^1,a*(p/q)^2,...,a*(p/q)^(n-1)
//假设抽取的数列  b0,b1,...,b(N-1)  (从小到大排好序了)
//  b1/b0,b2/b0,...,b(N-1)/b0  -->  (p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)
//那么我们在面对(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)的时候，该求什么东西呢
//首先明确一点，这些数字不一定是个等比数列，而是等比数列的某一部分，而且这个等比数列的
//公比不唯一我们要求的还//得是要可能的最大的一个公比。那么，针对一个不连续的等比数列，他
//们的共同点是，(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)这些每一个值肯定都是
//公比的倍数，那么它们的最大公约数不就是可能的最大公比了吗



//  我们要求的是：  （p/q）^k  //(p/q)>1,所以使k最大，即求（p/q）^x1~(p/q)^x(N-1)的最大公约数，其实就是求x1~x(N-1)的最大公约数
//这里我们使用更相减损术，因为我们没有得到确切的x1~x(N-1)是多少，我们只有(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)//这些的值

/*更相减损术：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得
减数和差相等为止，也就是是当较小者为0时退出。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。*/

//更相减损术总用较大的减去较小的
/*例子：
    98-63=35
    63-35=28
    35-28=7
    28-7=21
    21-7=14
    14-7=7
所以，98和63的最大公约数等于7。*/

//我们这里要用更相减损术的是指数，所以要让(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)，
//两两计算，互除(这样可以实现指数相减，我们本来就是求它们指数的最大公约数)，除到
//结果为1(任何数的零次方的值为1),即x1=x2,此时幂次为0，结果为1，这其实就是y总的思路，
//再次感叹y总的才华
//把分子分母分别去算，结果是相同的因为，分子分母的幂次是相同的
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()
{
    int n;
    cin>>n;

    for(int i=0; i<n; i++)  scanf("%lld",&x[i]);

    sort(x,x+n);

    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;  //得到x[i]/x[0]的分子
            b[cnt]=x[0] / d;  //得到x[i]/x[0]的分母
            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;
}