[CF798C] Mike and gcd problem（规律,gcd）

题目链接：http://codeforces.com/contest/798/problem/C

题意：给n个数，和一种操作：把a(i)和a(i+1)变成a(i)-a(i+1)和a(i)+a(i+1)。问能不能把整个数列变成gcd>1，能的话输出最少步骤。

贪心地认为假如需要这种操作，那么gcd为2是最好的。

进行操作无非四种情况：奇奇 奇偶 偶奇 偶偶。奇偶和偶奇可以看成一种情况，而偶偶则不需要进行操作。只剩下奇奇。

进行一次操作后，会发现奇奇会变成偶偶。

再看奇偶，奇偶进行一次会变成奇奇，再进行一次就是偶偶。

那么先把奇奇的处理了，再找奇偶，偶奇的情况就行了。

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

const int maxn = 100100;
int n, a[maxn];

int main() {
    // freopen("in", "r", stdin);
    while(~scanf("%d", &n)) {
        int g = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            g = __gcd(g, a[i]);
            if(a[i] & 1) a[i] = 1;
            else a[i] = 0;
        }
        if(g != 1) {
            puts("YES
0");
            continue;
        }
        int ret = 0;
        for(int i = 1; i < n; i++) {
            if(a[i] && a[i+1]) {
                a[i] = a[i+1] = 0;
                ret++;
            }
        }
        for(int i = 1; i <= n; i++) {
            if(a[i]) ret += 2;
        }
        printf("YES
%d
", ret);
    }
}