Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-最大公约数(C/C++/Java组)
题目 2709:

蓝桥杯2022年第十三届决赛真题-最大公约数(C/C++/Java组)

时间限制: 3s 内存限制: 512MB 提交: 1067 解决: 167

题目描述

给定一个数组,每次操作可以选择数组中任意两个相邻的元素 x, y 并将其中的一个元素替换为 gcd(x, y) ,其中 gcd(x, y) 表示 x 和 y 的最大公约数。

请问最少需要多少次操作才能让整个数组只含 1 。 

输入格式

输入的第一行包含一个整数 n ,表示数组长度。

第二行包含 n 个整数 a1, a2, · · · , an,相邻两个整数之间用一个空格分隔。 

输出格式

输出一行包含一个整数,表示最少操作次数。如果无论怎么操作都无法满足要求,输出 −1 。

样例输入

3
4 6 9

样例输出

4

提示

对于 30% 的评测用例,n ≤ 500 ,ai ≤ 1000;

对于 50% 的评测用例,n ≤ 5000 ,ai ≤ 106

对于所有评测用例,1 ≤ n ≤ 100000 ,1 ≤ ai ≤ 109

标签