线段树+二分，时间复杂度O(nlognlogn)

解题思路:见注释

注意事项:

参考代码:

#include<bits/stdc++.h>

//当数组中已经存在1时，设1的数量为numof1，显然每更新一次可以让一个不为1的数变为1，且最多可以让一个不为1的数变为1，所以最少要更新n-numof1次；

//当数组中不存在1时，如果所有元素的最大公因数不为1，显然永远不可能将任一个元素变为1，输出-1。

//                   否则，寻找长度最短的区间[l,r](长度记为len)，这个区间的最大公因数为1，那么使这个区间出现1需要len-1次，也就是先把a[l+1]变为

//gcd(a[l],a[l+1]),再把a[l+2]变为gcd(a[l+1],a[l+2])...最后把a[r]变为gcd(a[r-1],a[r])，显然最终a[r]就是1，共操作len-1次，再用这个1更新整个数组，共操作n-1次，

//所以一共操作len-1+n-1次。用二分寻找len，用线段树维护区间最大公因数。 

using namespace std;

#define maxn 100010

int n;

int a[maxn];

struct node{

int l;

int r;

int gcdval;//a[l]到a[r]这些数的最大公约数 

}tree[maxn<<2];

int gcd(int x,int y){

while(y){

x=x%y;

if(x==0)break;

y=y%x;

}

return max(x,y);

} 

void build(int idx,int l,int r){

tree[idx].l=l;tree[idx].r=r;

if(l==r){

tree[idx].gcdval=a[l];

}

else{

int mid=(l+r)>>1;

build(idx<<1,l,mid);

build(idx<<1|1,mid+1,r);

tree[idx].gcdval=gcd(tree[idx<<1].gcdval,tree[idx<<1|1].gcdval);

}

}

int search(int idx,int l,int r){

if(l<=tree[idx].l&&tree[idx].r<=r){

return tree[idx].gcdval;

}

//if(r<tree[idx].l||l>tree[idx].r)return 0;//这句话事实上不会运行到 

int gcdval1=0,gcdval2=0;

if(tree[idx<<1].r>=l){

gcdval1=search(idx<<1,l,r);

}

if(tree[idx<<1|1].l<=r){

gcdval2=search(idx<<1|1,l,r);

}

if(gcdval1==0||gcdval2==0)return max(gcdval1,gcdval2);

return gcd(gcdval1,gcdval2);

}

bool check(int len){

for(int i=1;i<=n-len+1;i++){

if(search(1,i,i+len-1)==1)return true;

}

return false;

}

int main(){

scanf("%d",&n);

int numof1=0;

for(int i=1;i<=n;i++){

scanf("%d",&a[i]);

if(a[i]==1)numof1++;

}

if(numof1){

printf("%d",n-numof1);return 0;

}

build(1,1,n);

if(check(n)==false){

printf("-1");return 0;

}

int l=1,r=n;

while(l<r){

int mid=(l+r)>>1;

if(check(mid))r=mid;

else l=mid+1;

}

printf("%d",l-1+n-1);

return 0;

}