Dễ thấy, để ~\text{gcd}(a_i, x) > 1~, cần tồn tại một số nguyên dương ~d > 1~ là ước của cả ~a_i~ và ~x~. Tuy nhiên, vì ta đang muốn cực tiểu ~x~, ta chỉ cần quan tâm tới các ước nguyên tố của ~a_i~. Nói cách khác, ~x~ sẽ là tích của các số nguyên tố khác nhau.

Ta có ~15~ số nguyên tố nhỏ hơn hoặc bằng ~50~, vì vậy ta có thể thử toàn bộ ~2^{15}~ trường hợp của ~x~, và tìm ra số nhỏ nhất thỏa mãn đề bài.

Độ phức tạp: ~O(2^{15} \cdot n \cdot g)~, với ~g~ là chi phí của hàm ~\text{gcd}~.

Code mẫu

#include <iostream>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cctype>
#include <cassert>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <string>
#include <ext/pb_ds/assoc_container.hpp>

// #define cerr if(false)cerr
#define see(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
    for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
        out << v[i] << " ";
    out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, set<T> &s) {
    for (auto e : s)
        out << e << " ";
    out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, multiset<T> &s) {
    for (auto e : s)
        out << e << " ";
    out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, queue<T> &s) {
    for (auto e : s)
        out << e << " ";
    out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, deque<T> &s) {
    for (auto e : s)
        out << e << " ";
    out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, pair<T, N> &p) {
    out << "(" << p.first << ", " << p.second << ") ";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
    for (size_t i = 0; i < v.size(); ++i)
        cout << v[i];
    out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, set<pair<T, N> > &s) {
    for (auto p : s)
        out << p;
    out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
    for (size_t i = 0; i < v.size(); ++i) {
        for (size_t j = 0; j < v[i].size(); ++j) {
            out << v[i][j] << " ";
        }
        out << "\n";
    }
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<set<T> > &v) {
    for (size_t i = 0; i < v.size(); ++i) {
        out << v[i];
    }
    out << "\n";
    return out;
}

long long gcd(long long a, long long b) {
    return (b == 0) ? a : gcd(b, a % b);
}

void sieve(vector<int> &primes) {
    for (int i = 2; i <= 100; ++i) {
        if (primes[i]) {
            for (int j = i + i; j <= 100; j += i) {
                primes[j] = 0;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;

    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }

    vector<int> prime(110, 1);
    sieve(prime);

    vector<int> potential_primes;
    for (int i = 2; i <= 50; ++i) {
        if (prime[i]) {
            potential_primes.push_back(i);
        }
    }

    long long ans = LLONG_MAX;
    for (int i = 0; i < (1 << 15); ++i) {
        long long curr_y = 1;
        for (int j = 0; j < 15; ++j) {
            if ((1 << j) & i) {
                curr_y *= potential_primes[j];
            }
        }

        bool coprime = false;
        for (int j = 0; j < n; ++j) {
            if (gcd(x[j], curr_y) == 1) {
                coprime = true;
                break;
            }
        }

        if (!coprime) {
            ans = min(ans, curr_y);
        }

    }

    cout << ans << "\n";

    return ;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    t = 1;

    while (t--) {
        solve();
    }

    return 0;

}