CF798C Mike and gcd problem 题解

· · 题解

先从只有两个数的情况开始考虑（设为 a 和 b）：

那么我们开始思考对于整个数组的操作：既然四种操作都导向偶数，那么最终整个数组都会变为偶数（因为奇数和偶数互质），除非整个数组一开始都是奇数且 \gcd(a_1,a_2,\cdots,a_n)>2。

所以我们可以将相邻奇数两两配对，每两个花费一次操作把他们变成偶数。如果还剩下一个奇数，那么它单独花费两次操作和旁边的偶数一起变成偶数。不会存在旁边没有偶数的情况，因为如果原数列全是奇数，要么 \gcd(a_1,a_2,\cdots,a_n)>2，要么换完以后会留下至少一个偶数。这也是这道题一定会有解的原因。

#include<bits/stdc++.h>
#define gcd __gcd
#define MAXN 100005
using namespace std;
int n,ans,a[MAXN];
signed main(){
    cin>>n;
    int g=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        g=gcd(g,a[i]);
    }
    if(g==1){
        int i=1,j=1;
        while(i<=n){
            j=i;
            if(a[i]%2==0) i++;
            while(j<=n&&a[j+1]%2) j++;
            ans+=(j-i+1)/2;
            if((j-i+1)%2) ans+=2;
            i=j+1; 
        } 
    }
    cout<<"YES\n";
    cout<<ans;
}