思路:
1.去重排序将其进行预处理
2.用gcd得到最简比值
3.用gcd_sub分别计算分子、分母的指数最大公约数
- #include
- using namespace std;
- const int N = 110;
- typedef long long ll;
- ll n, cnt, a[N], x[N], y[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 = 1; i <= n; i ++)
- {
- cin >> a[i];
- }
- sort(a + 1, a + 1 + n);
- for(int i = 2; i <= n; i ++)
- {
- if(a[i] != a[i - 1])
- {
- ll d = gcd(a[i], a[1]);
- cnt ++;
- x[cnt] = a[i] / d;//分子
- y[cnt] = a[1] / d;//分母
- }
- }
- ll u = x[1], d = y[1];
- for(int i = 2; i <= cnt; i ++)
- {
- u = gcd_sub(u, x[i]);
- d = gcd_sub(d, y[i]);
- }
- cout << u << '/' << d;
- return 0;
- }