CodeForces - 892C Pride

题意：给你一个长度为n的数组，每次可以进行一种操作把第i个数和第i+1个数替换为第i个数或者第i+1个数的gcd，问最少多少步能够使得序列全部变成1.

思路：这道题的只要数组里面有一个1 ，操作就变得简单了。如果只有一个1那么只要再执行n - 1步操作就可以全变成1，i个1就执行n-i步操作，就可以了，如果给的初始数组没有1那么我们就化出一个1来再加上n - 1，考虑每一段区间i ~ j(i < j)上的情况：记g(i,j)=gcd{a[i]|i=i,...,j}，则有以下递推关系式：g( i , j + 1 ) = gcd( g ( i , j ) , a [ j + 1])。若存在i < j，使得g(i，j)=1，令d=j - i，则有操作步数为n+d-1。注意这个操作步数的计算。在当前情况下，首先在区间i ~ j上构造出一个元素1：d步；再用这个1与其他元素作gcd运算：n-1步。于是总操作步数为n+d-1。于是，枚举i , j，求最小的d=j - i。

AC代码：

#include<stdio.h>
#define INF 100000000
#define maxn 2005

int n;
int ans[maxn];

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		gcd(b, a % b);
	}
}

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