CodeForces - 892C Pride GCD

http://codeforces.com/contest/892/problem/C

题意：给你一个数列，有操作：对于相邻两个数，可以替换其中一个数为这两个数的gcd。求多少次操作后该数列全为1，不存在输出-1。

题解：可以发现，①只要数列中出现了1，那么对于1相邻的数操作，将相邻的数变为1即可(操作次数是数列中剩下不为1的数)。②数列中不存在1，需要找出1(可能需要多次操作才会出现1)，那么对于原数列每个相邻的数求一次gcd，看是否出现了1。若没出现那么对于gcd再求一次gcd，知道只剩一个gcd(操作次数是反复求gcd至出现1的次数)。然后特判原数列就有1的情况，这里被hack了。

代码：

#include<bits/stdc++.h>
#define debug cout<<"aaa"<<endl
#define d(a) cout<<a<<endl
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;

const int N = 2000 + 5;
const int M = N * N + 5;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
int a[N];

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

int main(){
	int n,ans=-1,cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==1){
			cnt++;
		}
	}
	if(cnt!=0){
		printf("%d\n",n-cnt);
		return 0;
	}
	cnt=n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<cnt;j++){
			a[j]=gcd(a[j],a[j+1]);
			if(a[j]==1){
				ans=i;
				break;
			}
		}
		if(ans!=-1){
			ans=ans+n-1;
			break;
		}
		cnt--;
	}
	cout<<ans<<endl;
	return 0;
}