gcd, prefix, suffix

ac_abc125_c.cpp

// https://atcoder.jp/contests/abc125/tasks/abc125_c
// There are N integers,, written on the blackboard.
// You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), 
// possibly the same as the integer originally written.
// Find the maximum possible greatest common divisor of the  N integers on the blackboard after your move.

// Interesting prolem on precomputing prefix/suffix function
// In this case it is gcd which is associative as we know
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int n ; 
    cin >> n;
    vector<int> a(n+1,0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<int> prefGcd(n+1);
    prefGcd[0] = 0;
    for (int i = 1; i <= n; ++i)
        prefGcd[i] = __gcd(prefGcd[i-1], a[i]);

    vector<int> sufGcd(n+2);
    sufGcd[n+1] = 0;
    for (int i = n; i > 0; --i)
        sufGcd[i] = __gcd(sufGcd[i+1], a[i]);

    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res = max(res, __gcd(prefGcd[i-1], sufGcd[i+1]));
    }
    cout << res << endl;
    return 0;
}