No.3270 No Coprime Cycles
タグ : / 解いたユーザー数 14
作問者 :
apricity
/ テスター :
遭難者
問題文
正整数列 $B = (B_1,B_2,\dots,B_{|B|})$ に対して，以下の手順に従って構成される，辺に正整数のラベルが付いた無向グラフを $g(B)$ と表します．
- $g(B)$ を，頂点 $1$ から頂点 $|B|$ までの $|B|$ 頂点及び $0$ 辺からなるグラフで初期化する．
- $1 \le i < j \le |B|$ を満たす全ての整数組 $(i, j)$ に対して以下を行う．
- $B_i$ と $B_j$ の $\bm{2}$ 以上の公約数 全てからなる整数の集合を $S_{ij}$ とする． $S_{ij}$ の全ての要素 $d$ について，頂点 $i$ と頂点 $j$ を結ぶ，ラベル $d$ の無向辺を $g(B)$ に追加する．
長さ $N$ の正整数列 $A = (A_1,A_2,\dots,A_N)$ が与えられます．あなたは $A$ に対して以下の操作を $0$ 回以上任意の回数行うことができます．
- $1 \le i \le N$ を満たす整数 $i$ と $A_i$ の 正の約数 $x$ を選び， $A_i$ を $\dfrac{A_i}{x}$ で置き換える．この操作には $x$ のコストがかかる．
あなたの目標は， $A$ が以下の条件を満たすようにすることです．
- $g(A)$ の長さ $\bm{2}$ 以上 のサイクルであって，構成する各辺のラベルを割り切る最大の正整数が $1$ であるものが 存在しない ．
入力
$N$ $A_1\ A_2\ \dots\ A_N$
- 入力は全て整数
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^6$
出力
目標を達成するために必要なコストの総和として考えられる最小値を出力してください．
サンプル
サンプル1
入力
3 6 6 12
出力
4
頂点 $i$ と頂点 $j$ を結ぶラベル $\color{red}d$ の辺を $(i,j,{\color{red}d})$ と表します． $A = (6,6,12)$ に対して， $g(A)$ に存在する辺は以下の通りです．
- $(1,2,{\color{red}2})$
- $(1,2,{\color{red}3})$
- $(1,2,{\color{red}6})$
- $(1,3,{\color{red}2})$
- $(1,3,{\color{red}3})$
- $(1,3,{\color{red}6})$
- $(2,3,{\color{red}2})$
- $(2,3,{\color{red}3})$
- $(2,3,{\color{red}6})$
- 辺 $(1,2,{\color{red}2}), (2,3,{\color{red}3}), (1,3,{\color{red}6})$ から構成される長さ $3$ のサイクル． $2,3,6$ を割り切る最大の正整数は $1$ です．
- 辺 $(1,2,{\color{red}2}), (1,2,{\color{red}3})$ から構成される長さ $2$ のサイクル． $2,3$ を割り切る最大の正整数は $1$ です．
以下の操作により，コスト $4$ で条件を満たすことができます．
- $i = 1$, $x = 2$ を選び， $A_1 \leftarrow 3$ とする．
- $i = 2$, $x = 2$ を選び， $A_2 \leftarrow 3$ とする．
サンプル2
入力
4 1 2 4 8
出力
0
$A = (1,2,4,8)$ は条件を満たすので，一回も操作を行う必要がありません．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。