\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Thử từng giá trị từ \(x = 1 \rightarrow +oo\) nếu số nào thỏa mãn thì ta xuất \(x\) ra và dừng chương trình

Vì \(x\) phải là ước của các số trong mảng nên nếu \(x > min(A)\) thì không còn thỏa mãn và xuất \(-1\)

• Hoặc ta có thể tìm ước của từng số và duyệt kiểm tra xem ước nào thỏa mãn

Ước thỏa mãn là ước xuất hiện đúng \(n\) lần trong mảng

\(\color{orange}{\text{Hint 2 <Optimization>}}\)

• Nếu theo cách 1 thì gọi \(S\) là tập các ước số chung của cả mảng, rõ ràng các số trong tập \(S\) đều là ước của ước chung lớn nhất cả mảng

Nếu ước chung lớn nhất cả mảng là \(d\) mà \(d = 1\) thì xuất \(-1\) ngược lại xuất \(d\)

• Nếu theo cách 2 thì giả sử \(d\) là ước xuất hiện \(n\) lần trong mảng, thì các ước của \(d\) cũng thế

Mà ta cần tìm ước nhỏ nhất lớn hơn 1 nên số cân tìm sẽ là ước nguyên tố nhỏ nhất của \(d\)

\(\color{orange}{\text{Hint 3 <Optimization>}}\)

• Nếu theo cách 1, sau khi tìm được ước chung lớn nhất \(d\) và nếu \(d > 1\) ta sẽ tìm ước nguyên tố nhỏ nhất của \(d\)

Chúng ta chỉ cần duyệt các số trong đoạn \([2, \sqrt{d}]\) và nếu tìm thấy thì xuất ra

Còn không thì lúc này \(d\) chắc chẵn là số nguyên tố, vì nếu \(d = a \times b\) với \(1 < a < b < d\) thì \(a \leq \sqrt{d}\)

Hoặc ta có thể dùng sàng và xuất ra ước nguyên tố nhỏ nhất của \(d\) luôn nhưng không hiệu quả

• Nếu theo cách 2, gọi \(lpf[x]\) là ước số nguyên tố nhỏ nhất của \(x\) (ta có thể sàng trong thời gian tuyến tính)

Lúc này ta chỉ cần tính \(d = max(lpf[a_i])\) thì nếu mọi phần tử \(a_i\) đều là bội của \(d\) thì \(d\) thỏa mãn, ngược lại thì cả mảng không có ước chung lớn hơn 1

• Lưu ý rằng cách 1 lợi thế trong các bài toán truy vấn chèn thêm phần tử cũng như chỉ có \(O(1)\) bộ nhớ

\(\color{green}{\text{Preference AC Code }}\): Brute-force, Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n \log max\_val)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int n = readInt();
    int d = readInt();
    while (--n) d = gcd(d, readInt());

    if (d == 1)     return cout << -1, 0;
    if (d % 2 == 0) return cout << 2, 0;
    for (int i = 3; i <= d; i += 2)
        if (d % i == 0)
            return cout << i, 0;

    return 0;
}

\(\color{green}{\text{Preference AC Code }}\): Brute-force, Sieving

\(^{^{\color{purple}{\text{Complexity : }} O(n + max\_val)\ \color{purple}{\text{time}}\ ||\ O(n + max\_val)\ \color{purple}{\text{memory}}}}\)

vector<int> prime, lpf;
void sieve(int lim = LIM)
{
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    for (int i = 3; i <= lim; i += 2)
    {
        if (lpf[i] == 2) prime.pb(lpf[i] = i);
        for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && i * prime[j] <= lim; ++j)
            lpf[i * prime[j]] = prime[j];
    }
}

int main()
{
    int n = readInt();

    int mx = 0;
    vector<int> a(n);
    for (int &x : a)
    {
        cin >> x;
        mx = max(mx, x);
    }

    int d = 1;
    for (int x : a)
        d = max(d, lpf[x]);

    for (int x : a)
        if (x % d != 0)
            return cout << -1, 0;

    cout << d;
    return 0;
}