ABC191 F GCD or MIN
まず重要な考察としてとりうる数は元の数列の最小値より小さくなることはない, ということが挙げられる. なぜなら$ gcd(x,y) \leq min(x,y)が成り立つからである.
また実験をしてみると, いくつかgcdをとって, その後他とのminをとるという場合に限定しても答えは変わらないことがわかる. 結局, 答えは$ min(min\{A_i\}, gcd(Aの部分集合))となる. よって$ gcdの部分を高速に計算できれば良い.
ここで$ gcdの候補になりうるのは$ A_iの約数のみであるので, 連想配列を用いて適切に実装することで答えを求めることができる. 計算量は$ x以下の正整数の約数の個数の最大値を表す関数を$ d(x)とおくと, $ O(max(Nd(max\{A_i\}), d(max\{A_i\} \log d(max\{A_i\})))となり, これは十分高速である.