题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a;
ll gcd(ll a,ll b)
{
    ll r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void ggcd(ll &a1,ll &b1,ll a2,ll b2)
{
    while(a2>b2)
    {
        ll x=gcd(a1,b1);
        a1/=x,b1/=x;
        x=gcd(a2,b2);
        a2/=x,b2/=x;
        while(a1>=a2&&b1>=b2)a1/=a2,b1/=b2;
        swap(a1,a2);
        swap(b1,b2);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    bool f=0;
    vector<ll>v;
    for(int i=0;i<n;i++)
        scanf("%lld",&a),v.push_back(a);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    ll a1=1,b1=1;
    for(int i=1;i<v.size();i++)
        ggcd(a1,b1,v[i],v[i-1]);    
    ll x=gcd(a1,b1);
    cout<<a1/x<<'/'<<b1/x<<'\n';
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla