题意：已知长度为n的序列a，要求序列gcd  a(a1,a2,a3,a4……an)不为1。求最少的操作次数，使得满足条件。每次操作，可以把a[i]  a[i+1] 变为  a[i]-a[i+1]   a[i]+a[i+1]。


思路：求最少的操作次数，那我们要看操作对结果的影响。 假设两个相邻的数为A,B。 那么经过以下操作 A,B→A-B,A+B→ -2B,2A 。

如果相邻的数都是偶数，再怎么减，结果都是2的倍数，无用功。

如果相邻的数都是奇数，那么经过1次操作就可以变成2的倍数

如果一个是奇数，一个是偶数，那么经过2次操作就可以变成2的倍数。

那么肯定会有疑惑，为什么一定要是2的倍数呢？（不会证明，也没有找到合适的证明方法，仿佛这样是行得通的）


数据：2 ≤ n ≤ 100 000


复杂度：O( n*log2( max(a[i]) ) ) 撑死1e5*log2(1e9)≈3e6


CODE：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=1e5+50;
int a[maxn];

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

int main(void)
{
    int n;
    cin >> n;
    ll GCD=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        GCD=gcd(GCD,a[i]);
    }
    if(GCD!=1)
    {
        printf("YES\n0\n");
        return 0;
    }
    ll ans=0;
    for(int i=1;i<=n-1;i++)
        if(a[i]&1 && a[i+1]&1)
            a[i]=a[i+1]=2,ans++;
    for(int i=1;i<=n;i++)
        if(a[i]&1)
            ans+=2;
    cout <<"YES"<<endl;
    cout << ans << endl;
}