AcWing 1223. 最大比例
原题链接
中等
作者:
wjie
,
2020-07-09 20:09:42
,
所有人可见
,
阅读 877
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 105;
LL arr[N];
int idx;
struct Node{
LL x;
LL y;
}nodes[N];
LL gcd(LL a, LL b)
{
if (a % b == 0)
return b;
return gcd(b, a%b);
}
LL gcdSub(LL a, LL b)
{
if (a < b)
swap(a, b);
if (b == 1)
return a;
return gcdSub(b, a/b);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%lld", &arr[i]);
sort(arr, arr+n);
for (int i = n-1; i > 0; --i)
{
if (arr[i] != arr[i-1])
{
LL tmp = gcd(arr[i], arr[i-1]);
nodes[idx++] = {arr[i]/tmp, arr[i-1]/tmp};
}
}
LL resX = nodes[0].x, resY = nodes[0].y;
for (int i = 1; i < idx; ++i)
{
resX = gcdSub(resX, nodes[i].x);
resY = gcdSub(resY, nodes[i].y);
}
printf("%lld/%lld", resX, resY);
return 0;
}