ABC125C - GCD on Blackboard

Problem summary

There is $N$ numbers $A_1, A_2, \ldots , A_n$ .
You can change a number between $1$ and $10^9$ or do nothing.
Calculate maximum GCD of N numbers after rewriting.

Constraints

・Time limit: 2 sec
・Memory limit: 1024 MB
・Each input is an integer number.
・ $2 \leq N \leq 10^5$
・ $1 \leq A_i \leq 10^9$

Answer

You should calculate maximum GCD of N-1 numbers which have N choices.

blute-force

You can remove $A_i ( 1 \leq i \leq N)$ and simulate. This solution is $O(N^2)$

optimize

Prepare two sequences $l$ and $r$ such that
$l[i] = GCD(A_1, A_2, \ldots, A_i)$
$r[i] = GCD(A_n, A_{n-1}, \ldots, A_i)$
and calculate
$MAX(MAX_{i=2}^{n-1}{(GCD(l[i-1], r[i+1]))}, l[n-1], r[2])$ .
This solution takes $O(N)$