Submission #6029907

---

Source Code Expand

// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

static constexpr int mod = (int)1e9 + 7;
static constexpr int inf = 100100100;
static constexpr ll linf = 1e18;
static constexpr double eps = 1e-9;
static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, n) for (ll i = n; i >= 0; --i)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define pb push_back
#define ist insert
#define fst first
#define snd second


template <typename T>
T gcd(T a, T b) {
    while (b != 0) {
        T c = a;
        a = b;
        b = c % b;
    }
    return a;
}

template <typename T>
vector<T> prime_factorize(T num) {
    assert(num > 1);
    vector<T> factor;
    T n = sqrt(num) + 1;
    for (T i = 2; i < n; ++i) {
        while (num % i == 0) {
            num /= i;
            factor.push_back(i);
        }
    }
    if (num > 1) {
        factor.push_back(num);
    }
    return factor;
}

map<ll, vector<ll>> cache;
map<ll, vector<ll>> F;

int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> A;
    rep (i, N) {
        ll a;
        cin >> a;
        A.pb(a);
    }
    for (ll a : A) {
        if (a > 1) {
            if (!cache.count(a)) {
                cache[a] = prime_factorize(a);
            }
            for (ll p : cache[a]) {
                F[p].pb(a);
            }
        }
        F[1].pb(a);
    }
    ll ans = 1;
    for (auto f : F) {
        if (f.snd.size() >= A.size() - 1) {
            ll g = f.snd[0];
            for (ll x : f.snd) {
                g = gcd(g, x);
            }
            ans = max(ans, g);
        }
    }
    cout << ans << endl;
}

Submission Info

Judge Result