問題一覧 > 通常問題

No.2756 GCD Teleporter

レベル : / AI推定難易度 : 1625 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 54
作問者 : MZKi / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 9351 / 自分の提出
問題文最終更新日: 2023-03-23 21:32:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 429 (順位表) の他の問題:

Problem Statement

There is a sugoroku board consisting of $N$ squares, and a positive integer $A_i$ is written on the $i$-th square. Initially, a piece is placed on the $1$-st square.

On this board, the piece can warp to a square on which is written an integer that is not coprime with the integer written on the square where the piece currently is, and there is no other way to move. Before the sugoroku starts, you may perform the following operation any number of times, possibly $0$.

  • Choose $i$ with $1 \le i \le N$ and a positive integer $m$, pay a cost of $m$, and multiply $A_i$ by $m$.

Find the minimum total cost required so that the piece can be moved from the $1$-st square to every other square from the $2$-nd to the $N$-th using some number of warps.

Input

$N$
$A_1\ A_2\ \dots\ A_N$

  • $2 \le N \le 2 \times 10^5$
  • $1 \le A_i \le 2 \times 10^5\ (1 \le i \le N)$
  • All inputs are integers.

Output

Output the minimum total cost, followed by a newline.

Sample

Sample 1
Input
4
1 2 3 4
Output
4

It is optimal to multiply the $1$-st square by $2$ and the $3$-rd square by $2$.

Sample 2
Input
4
6 4 3 9
Output
0

The condition may already be satisfied from the beginning.

Sample 3
Input
4
3 3 3 5
Output
3

It is optimal to multiply the $4$-th square by $3$.

Sample 4
Input
10
42 39 59 67 71 9 78 37 19 4
Output
10

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。