AcWing 1223. 最大比例
原题链接
中等
作者:
Phyllis
,
2025-03-25 11:04:49
·广东
,
所有人可见
,
阅读 1
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 110;
ll a[N], b[N], x[N];
ll n;
ll gcd(ll a, ll b)
{
if(b == 0) return a;
else return gcd(b, a % b);
}
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 ++) scanf("%lld", &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[0], x[i]);
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]);
}
printf("%lld/%lld\n", up, down);
return 0;
}