CF891A Pride

题目

A. Pride

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

Copy

5
2 2 3 4 6

output

5

Copy

4
2 4 6 8

output

-1

Copy

3
2 6 9

output

4

题解

• 如果有x个1,那么显然答案为n-x
• 如果没有1,考虑最少需要多少操作弄出一个1来,考虑到gcd(x,y)赋值给y更好,因为gcd(x,y)已经少了一些因子,然后问题就转化为求最短的区间使得gcd(L,R)为1.gcd(L,R+1)=gcd(gcd(L,R),a[R+1]))可以O(n^2)求出所有区间的gcd值.
• 另外这种枚举的方式我觉得挺妙的

代码

#include<cstdio>
#include<cstring>
#define min(a,b) (a<b?a:b)
const int MAXN=2007;
const int INF=1e9+7;
int a[MAXN][MAXN];
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	int n;scanf("%d",&n);
	int cnt1=0;
	for(int i=0;i<n;++i){
		scanf("%d",&a[i][i]);
		if(a[i][i]==1)++cnt1;
	}
	if(cnt1!=0){
		printf("%d\n",n-cnt1);
		return 0;
	}
	int ans=1e9+7;
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			a[i][j]=gcd(a[i][j-1],a[j][j]);
			if(a[i][j]==1)ans=min(ans,j-i);
		}
	}
	if(ans==INF)printf("-1");
	else printf("%d\n",n-1+ans);
	return 0;
}