st复习
st[i][j]代表的是[i,i+2^j-1]这个区间内的元素

这个题的思路是怎么花费最小的代价先构造出一个1来，之后其他剩余元素就可以被这个一个1扩展出来。
先用st表预处理出来所有区间gcd，二分答案寻找最短区间。(这里其实用双指针更好)
不考虑特殊情况的时候，假设最短区间为l,那么结果就是l-1+n-1。l-1就是让区间结果为1的步骤数。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 1e5+6;
int a[N],n;
int st[N][20],lg[N],pw[20];
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
int query(int l,int r){
    int k=lg[r-l+1];
    return gcd(st[l][k],st[r+1-(1<<k)][k]);
}
bool check(int x){
    //判断是否存在一个长度为x的区间，使得答案gcd为1
    for(int i=1;i+x-1<=n;i++){
        if(query(i,i+x-1)==1)return true;
    }
    return false;
}
int main(){
    scanf("%d",&n);
    int cnt_1=0;
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++){
        scanf("%d",&st[i][0]);
        if(st[i][0]==1)
            cnt_1++;
    }
    if(cnt_1){
        cout<<n-cnt_1;
        return 0;
    }
    for(int l=1;(1<<l)<=n;l++){
        for(int i=1;i+(1<<l)-1<=n;i++){
            st[i][l]=gcd(st[i][l-1],st[i+(1<<(l-1))][l-1]);
        }
    }
    if(query(1,n)!=1){
        puts("-1");
        return 0;
    }
    int ans=n+1;
    int l=1,r=n,mid=0;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    cout<<l-1+(n-1);
    return 0;
}