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;
}