#P1408. 互质数列sequence

互质数列sequence

题目描述

一个数列有 nn 个数字,我们定义一种操作:我们可以将相邻两个数字同时除以它们的一个公约数,这个操作所花费的代价为作为除数的这个公约数的值。我们经过若干次这样操作,可以将原数列变为相邻的数对都互质的数列。问达成要求的最小代价。

输入格式

第一行一个正整数 nn

接下来 nn 行,每行一个整数,依次表示数列中的每个数字。

输出格式

输出最小代价。

3
3
12
6

5

提示

  • 30%30\% 数据满足 n20n \leq 20
  • 100%100\% 数据满足 1n100001 \leq n \leq 10000,数列中的数字 1Ai2×1071\le A_i \leq 2 \times 10^7