最大比例

题目描述

解析

接下来就是求解k和p的过程
在这道题中很难使用欧几里得算法就求解最大公约数
因此尝试使用另一种方法——更相减损术（循环相减法）

如果要使用欧几里得算法的话，就需要开一个非常复杂的根号，非常难算

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
int n;
ll a[N];
ll z[N], m[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 >> a[i];
    sort(a, a + n);
    int k=0;
    for (int i = 1; i < n; i++)
    {
        if (a[i-1] != a[i])
        {
            ll g = gcd(a[0], a[i]);
            z[k]=a[i]/g;
            m[k]=a[0]/g;
            k++;
        }
    }
    ll up=z[0];
    for(int i=1;i<k;i++) up=gcd_sub(up,z[i]);
    ll down=m[0];
    for(int i=1;i<k;i++) down=gcd_sub(down,m[i]);
    cout<<up/gcd(up,down)<<"/"<<down/gcd(down,up)<<endl;
    return 0;
}