English · Original
Chinese · Translation
Formal · Original
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?
## Input
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_ ≤ 109) — the elements of the array.
## Output
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.
[samples]
## Note
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.
你有一个长度为 $n$ 的数组 $a$，你可以执行操作。每个操作如下：选择数组 $a$ 中两个**相邻**的元素，记为 $x$ 和 $y$，并将其中一个替换为 $\gcd(x, y)$，其中 $\gcd$ 表示最大公约数。
你需要多少次最少的操作，才能使所有元素都变为 $1$？
输入的第一行包含一个整数 $n$ ($1 ≤ n ≤ 2000$) —— 数组中元素的个数。
第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$) —— 数组的元素。
如果不可能将所有数字变为 $1$，请输出 _-1_。否则，请输出使所有数字等于 $1$ 所需的最少操作次数。
在第一个样例中，你可以通过以下 $5$ 步操作将所有数字变为 $1$：
我们可以证明，在这种情况下，不可能用少于 $5$ 步操作使所有数字变为 $1$。
## Input
输入的第一行包含一个整数 $n$ ($1 ≤ n ≤ 2000$) —— 数组中元素的个数。第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$) —— 数组的元素。
## Output
如果不可能将所有数字变为 $1$，请输出 _-1_。否则，请输出使所有数字等于 $1$ 所需的最少操作次数。
[samples]
## Note
在第一个样例中，你可以通过以下 $5$ 步操作将所有数字变为 $1$： $[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$。
Let $ a = [a_1, a_2, \dots, a_n] $ be an array of positive integers.
Define $ g = \gcd(a_1, a_2, \dots, a_n) $.
If $ g \neq 1 $, output $-1$.
Otherwise, let $ k $ be the number of elements in $ a $ equal to $ 1 $.
If $ k > 0 $, then the minimum number of operations is $ n - k $.
If $ k = 0 $, let $ m $ be the minimum length of a contiguous subarray of $ a $ whose GCD is $ 1 $.
Then the minimum number of operations is $ (m - 1) + (n - 1) $.
That is:
$$
\text{Answer} =
\begin{cases}
-1 & \text{if } \gcd(a_1, \dots, a_n) \ne 1 \\
n - k & \text{if } k > 0 \\
(m - 1) + (n - 1) & \text{if } k = 0
\end{cases}
$$
where $ k = |\{ i : a_i = 1 \}| $, and $ m = \min\{ \ell : \exists i \text{ s.t. } \gcd(a_i, a_{i+1}, \dots, a_{i+\ell-1}) = 1 \} $.
API Response (JSON)
{
"problem": {
"name": "C. Pride",
"description": {
"content": "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_)",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF892C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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_)...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你有一个长度为 $n$ 的数组 $a$，你可以执行操作。每个操作如下：选择数组 $a$ 中两个**相邻**的元素，记为 $x$ 和 $y$，并将其中一个替换为 $\\gcd(x, y)$，其中 $\\gcd$ 表示最大公约数。\n\n你需要多少次最少的操作，才能使所有元素都变为 $1$？\n\n输入的第一行包含一个整数 $n$ ($1 ≤ n ≤ 2000$) —— 数组中元素的个数。\n\n第二行包含 $n$ ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ a = [a_1, a_2, \\dots, a_n] $ be an array of positive integers.\n\nDefine $ g = \\gcd(a_1, a_2, \\dots, a_n) $. \nIf $ g \\neq 1 $, output $-1$.\n\nOtherwise, let $ k $ be the number of elements in $ a ...",
"is_translate": false,
"language": "Formal"
}
]
}