Codeforces Round #446 (Div. 2) B(数论,模拟,gcd,最大公约数)

C. Pride

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You have an array a with length n, you can perform operations. Each operation is like this: choose two adjacent elements from a, say xand 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?

Input

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.

Output

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.

Examples

input

Copy

5
2 2 3 4 6
output

Copy

5
input

Copy

4
2 4 6 8
output

Copy

-1
input

Copy

3
2 6 9
output

Copy

4
Note

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.

题意:

一个数组,数组中可以相邻两个的求gcd,然后赋给任意一个,

求最快把数组中所以都变成1的步数

如果变不出,输出-1

解析:

如果所有的数的最大公约数gcd(a1,a2,a3,a4,......)不是1,呢么不论怎么变换,都只能变换成总gcd,出现无解

如果a1~an中存在一个1,呢么ans=n-sum(1)

gcd(a1,a2,a3,a4,....)=先求a1和a2gcd,赋给a2,再求a2和a3的gcd,赋给a3,类推

gcd(a,b,c,d)=gcd(gcd(gcd(a,b),c),d)

我们需要找出最小长度的区间    l~r,    gcd(a[l],..,a[r])=1    暴力模拟

ac:

#include<bits/stdc++.h>
#define MAXN 2005
#define ll long long
using namespace std;//先变一个1出来

ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

int a[MAXN]={0};

int main()
{
    int n,ans=999999,sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]!=1)
            sum++;
    }
    if(sum!=n)
    {
        printf("%d\n",sum);
    }
    else{
        for(int i=1;i<n;i++)
        {
            int t=a[i];
            for(int j=i+1;j<=n;j++)
            {
                t=gcd(t,a[j]);
                if(t==1)
                    ans=min(ans,j-i);
            }
        }
        if(ans>=2000)
            printf("-1\n");
        else printf("%d\n",ans+n-1);
    }
    return 0;
}