[Codeforces] Codeforces Round #669 B. Big Vova

問題

方針

配列 \( a \) を入れ替えて得られる配列を \( b \) とします。ここで、\( g(a, b) \) を \( a, b \) の最大公約数とします。次に配列 \( c \) の \( i \) 番目の要素を

\[ c_i = g(b_1, b_2, \cdots, b_i)\]

とします。このとき、得られる \( c \) の中で辞書式順序が最大であるときの \( b \) を求めます。

まず初めに、\( b_1 = \max(a_1, a_2, \cdots, a_n) \) であることが分かります。ここで、\( g_1 = b_1 \) とします。次に、\( g(g_1, a_i) \) を最大化する \( i \) を求めます。そして、\( b_2 = a_i \) となります。ただし、\( a_i \) は \( b \) の要素に含まれないものとします。同様にして、\( g_2 = g(g_1, a_i) \) とし、\( g(g_2, a_i) \) を最大化するものを求めます。

\( O(N^2) \) の計算量となります。

コード