CodeForces 892C Pride

题目大意

题目链接 给你一个长度为n的数组a。每次操作你可以选择相邻的两个位置a[i],a[i+1]，将其中某一个数用gcd(a[i],a[i+1])来代替。 你的目标是最后将a中所有元素都变成1，问最少需要多少次操作。如果无论怎样最后a数组不能全变成1，那么输出-1；否则输出最少需要多少次操作。

题解

做过一次了。 一开始的思路是，找俩最近且gcd=1的数，这两个数之间数的个数（含这俩数）-1就是将一个数组中的其中一个数换为1的最小次数，但是wa了；看cf数据后发现42 15 35按我的输出为-1，但实际为4. 这时候我就试着将每相邻的两个取gcd，若没有1，则对gcd再取gcd，直到某一层出现了1终止，这就代表了将数组中的其中一个数变为1的最小次数。 得到一个1之后便可以与其他数进行操作。 注意：若初始数组中已经包含1的情况！ wa两发，第一发是“注意”中提到的，第二发是按一开始的思路写的。

虽然还是错了两发，虽然是第二次做了，但是感觉思路明晰比上次清晰了，知道如何尝试着找突破口了。

代码

#include
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 2e3+10;
int res = INF;
int n, a[N], flag, cnt;

int main() {
	cin>>n;
	for(int i = 1;i >a[i], a[i] == 1?cnt++:cnt;
	if(cnt) {
		cout