UOJ Logo Universal Online Judge

UOJ

#497. 新年的复读机

附件下载 统计

春节前夕,米奇在钟楼上捡到了一台的复读机,这台复读机不仅可以自动复读,还可以用来求一个数列中所有数的最大公约数。

这台机器的使用方法是这样的,初始输入一个长度为 $n$ 的数列,第 $i$ 个数为 $a_i$($1 \le i \le n$)。

每次,米奇可以选择相邻的两个数 $a_i, a_{i+1}$,并向机器中投入恰好为这两个数的和的金币,也即 $a_i + a_{i+1}$。然后,机器就会自动计算出这两个数字的最大公因数,并用它替换这两个相邻的数,替换的位置为这两个数的位置。反复执行这个操作,直到机器中的数列只剩下一个数,这个数就是答案。

正所谓不想当复读机修理工的有钱鼠不是好数学家,米奇想知道,至少使用多少个金币,才能算出答案。

输入格式

第一行一个正整数 $n$,表示数列的长度。

第二行 $n$ 个正整数 $a_i$,表示这个数列。

输出格式

一行一个整数,表示最小使用的金币数。

样例一

input

7
33 33 66 6 66 22 22

output

260

explanation

一开始,序列为 $[33, 33, 66, 6, 66, 22, 22]$。

第一步,合并 $a_4, a_5$,得到 $[33, 33, 66, 6, 22, 22]$。

第二步,合并 $a_4, a_5$,得到 $[33, 33, 66, 2, 22]$。

第三步,合并 $a_3, a_4$,得到 $[33, 33, 2, 22]$。

第四步,合并 $a_2, a_3$,得到 $[33, 1, 22]$。

第五步,合并 $a_1, a_2$,得到 $[1, 22]$。

第六步,合并 $a_1, a_2$,得到 $[1]$。

总代价为 $(6 + 66) + (6 + 22) + (66 + 2) + (33 + 2) + (33 + 1) + (1 + 22) = 260$。

样例二

见样例数据下载。

限制与约定

子任务编号$n$分值
$1$$\le 500$$5$
$2$$\le 1000$$15$
$3$$\le 3000$$15$
$4$$\le 3\times 10^4$$30$
$5$$\le 2\times 10^5$$35$

对于所有数据,保证 $1\le n\le 2\times 10^5, 1\le a_i \le 10^{12}$。

时间限制:$\texttt{2s}$

空间限制:$\texttt{1024MB}$

下载

样例数据下载