Pride，DP题，本题关键就是找到一段最短区间[l,r]，该区间的gcd是1。详见本文内容

A. Pride

限制

time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

描述

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.
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 \le n \le 2000)$ — the number of elements in the array.
The second line contains $n$ space separated integers $a_1,a_2,…,a_n$ $(1 \le a_i \le 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$.

提示

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.

思路

dp数组中只有右上半个数组实际被用到。第25行的i是循环的区间长度，从1到n-1。第26行的j循环的是区间的起始元素。

__gcd(a, b)algorithm库中的函数