Pride
题意翻译
## 问题描述
你有一个长度为 $n$ 的数列 $a$,你能执行一些操作。每个操作是这样的:选择两个相邻的数 $x$ 和 $y$,把它们中的一个换为 $\gcd(x,y)$。这里的 $\gcd$ 代表[最大公约数](en.wikipedia.org/wiki/Greatest_common_divisor)。
问你把数列中的数全变成 $1$ 的最小操作次数。
## 输入格式
第一行是一个整数 $n$($1 \leq n \leq 2000$)——数列中数的个数。
第二行包含 $n$ 个分开的整数 $a_1,a_2,\ldots,a_n$($1 \leq a_i \leq 10^9$)——这个数列。
## 输出格式
如果不可能全变成 $1$,输出 $-1$。否则,输出把数列中的数全变成 $1$ 的最小操作次数。
## 说明
在第一个例子中你可以把数都变成 $1$ 通过这 $5$ 步:
- $[2,2,3,4,6]$
- $[2,1,3,4,6]$
- $[2,1,3,1,6]$
- $[2,1,1,1,6]$
- $[1,1,1,1,6]$
- $[1,1,1,1,1]$
可以证明在这个例子中不可能用 $5$ 步以下来把所有的数都变成 $1$。
题目描述
You have an array $ a $ with length $ n $ , you can perform operations. Each operation is like this: choose two adjacent elements from $ a $ , say $ x $ and $ y $ , and replace one of them with $ gcd(x,y) $ , where $ gcd $ denotes the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).
What is the minimum number of operations you need to make all of the elements equal to $ 1 $ ?
输入输出格式
输入格式
The first line of the input contains one integer $ n $ ( $ 1<=n<=2000 $ ) — the number of elements in the array.
The second line contains $ n $ space separated integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — the elements of the array.
输出格式
Print -1, if it is impossible to turn all numbers to $ 1 $ . Otherwise, print the minimum number of operations needed to make all numbers equal to $ 1 $ .
输入输出样例
输入样例 #1
5
2 2 3 4 6
输出样例 #1
5
输入样例 #2
4
2 4 6 8
输出样例 #2
-1
输入样例 #3
3
2 6 9
输出样例 #3
4
说明
In the first sample you can turn all numbers to $ 1 $ using the following $ 5 $ moves:
- $ [2,2,3,4,6] $ .
- $ [2,1,3,4,6] $
- $ [2,1,3,1,6] $
- $ [2,1,1,1,6] $
- $ [1,1,1,1,6] $
- $ [1,1,1,1,1] $
We can prove that in this case it is not possible to make all numbers one using less than $ 5 $ moves.