4358: T1 团结（unite）

内存限制：512 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：5 解决：1

题目描述

T1 团结（unite）

题目描述

小 C 有一个长度为 nn 的序列 AA。

小 C 认为一个序列 AA 是团结的当且仅当 gcd⁡(A1,A2,...,An)=1\gcd(A_1,A_2,...,A_n)=1。

小 C 现在可以做以下操作任意次：

  • 选择一个位置 ii，将 AiA_i 变为 gcd⁡(Ai,i)\gcd(A_i,i)，花费的代价为 n−i+1n-i+1。

小 C 想求出使序列 AA 团结的最小代价和。

输入

输入格式

输入的第一行包含一个整数 nn。

接下来一行包含 nn 个整数，第 ii 个整数表示 AiA_i。

输出

输出格式

输出共一行，包含一个整数，表示最小代价和。

样例输入 复制 

2
2 4

样例输出 复制 

2

提示

样例 1 输入

2
2 4

样例 1 输出

2

样例 1 解释

花费代价 22 选择位置 11，A1A_1 变为 11。

样例 2 输入

3
3 6 9

样例 2 输出

2

其余样例见下发文件。

数据规模与约定

  • 对于 3030% 的数据，保证 n≤20n\le 20。

  • 对于 6060% 的数据，保证 n≤50n\le 50。

  • 对于 100100% 的数据，1≤n≤1051\le n\le 10^5，1≤Ai≤1091\le A_i\le 10^9。

来源/分类

提交提交记录统计露一手!