蓝桥杯国赛_最大公约数

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n, a[100000 + 99], lo[100000 + 9], f[100009][20],cnt;

int gcd(int ma,int mi){
    return mi?gcd(mi,ma%mi):ma;
}

inline int rmq_gcd(int l,int r){
    int k=lo[r-l+1];
    return gcd(f[l][k],f[r-(1<<k)+1][k]);
}

int ck(int l,int r){
    return rmq_gcd(l,r)==1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a[1];
    f[1][0] = a[1];
    cnt+=a[1]!=1;
    for (int i = 2; i <= n; ++i)
    {
        cin >> a[i];
        cnt+=a[i]!=1;
        f[i][0] = a[i];
        lo[i] = lo[i >> 1] + 1;
    }
    for (int j = 1; j <= 17; ++j)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    if(!ck(1,n)){
        cout<<"-1";
        return 0;
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;++i){
        if(!ck(i,n))continue;
        int l=i,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(ck(i,mid))r=mid;
            else l=mid+1;
        }
        if(r==i)ans=min(ans,cnt);
        else ans=min(ans,r-i+cnt-1);
    }
    cout<<ans;
    return 0;
}