Codeforces Round #446 (Div. 2) C. Pride【】
2 seconds
256 megabytes
standard input
standard output
You have an array a with length n, you can perform operations. Each operation is like this: choose two adjacentelements 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 ≤ n ≤ 2000) — the number of elements in the array.
The second line contains n space separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — 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.
5
2 2 3 4 6
5
4
2 4 6 8
-1
3
2 6 9
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
最新文章
- Coding Kata - 挑战你的“底线”
- mac下apache配置,解决It is not safe to rely on the system's timezone settings.
- [转]ASP.NET MVC IOC 之AutoFac攻略
- Spring回调方法DisposableBean接口
- 多线程要点--CLR C#学习笔记
- c扩展调用php的函数(调用实现php函数的c函数)
- 《C程序设计语言现代方法》第5章 编程题
- ZIP压缩文件夹中上个月的文件,并将备份文件拷贝到服务器
- ios新特性
- ASP.NET页面传值与跳转
- 《JS权威指南学习总结--9.5 类和类型》
- 情景linux--如何摆脱深路径的频繁切换烦恼?
- R︱sparkR的安装与使用、函数尝试笔记、一些案例
- appJSON[";window";][";navigationBarTextStyle";] 字段需为 black 或 white
- Git在已有的分支上新建个人分支开发
- nc 使用实例
- python中的顺序表
- get、post的区别
- ARCore中四元数的插值算法实现
- django交互vue遇到的问题