A11419. Pride
编程题
普及/提高-
知识点
题目描述
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$ ?
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.
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.
- $[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.