[CF798C] Mike and gcd problem

Description

Mike 给定一个 (n) 个元素的整数序列 (A=[a_1,a_2,...,a_n])，每次操作可以选择一个 (i (1 le i<n))，将 (a[i],a[i+1]) 变成 (a[i]-a[i+1]) 和 (a[i]+a[i+1])。现在想要的是 (A) 序列所有元素的最大公约数大于 (1)，请计算最少的操作次数。

Solution

原始序列的 GCD 为 1 时，我们只需要将其变为 2

考虑两个数如何变成全偶数：两个奇数需要 (1) 次操作，一个奇数一个偶数需要 (2) 次操作

于是我们把原序列提出奇偶性后，先扫一遍处理掉所有相邻的奇数，再扫一遍处理掉所有一个奇数一个偶数的情况即可

无解是不会无解的

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

const int N = 1000005;
int n,a[N],g,ans;

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) g=__gcd(a[i],g);
    if(g>1) {
        cout<<"YES
0"<<endl;
    }
    else {
        for(int i=1;i<=n;i++) a[i]%=2;
        for(int i=1;i<n;i++) if(a[i]&a[i+1]) a[i]=a[i+1]=0, ++ans;
        for(int i=1;i<n;i++) if(a[i]^a[i+1]) a[i]=a[i+1]=0, ans+=2;
        cout<<"YES
"<<ans;
    }
}