思路：

首先如果数列的最大公约数大于1，直接输出即可。

否则，设对原数列中的a_i和a_i+1进行一次操作，分别变为a_i - a_i+1和a_i + a_i+1。设新数列的最大公约数为d，则由于d|(a_i - a_i+1)并且d|(a_i + a_i+1)得到d|(2a_i)且d|(2a_i+1)。则d|gcd(a₁, a₂, ..., 2a_i, 2a_i+1, a_i+2, ..., a_n)|2gcd(a₁, a₂, ..., a_n) = 2。说明进行一次这样的操作最多可以把最大公约数变为原来的2倍。所以我们的目标就是把数列的最大公约数变成2（即把所有的数都变成偶数）。

奇数 + 奇数 = 偶数，奇数 + 偶数 = 奇数，偶数 + 偶数 = 偶数。把奇偶性不同的相邻的两个数都变成偶数需要2次操作，而把相邻的两个奇数都变成偶数需要1次操作，所以首先优先把相邻的奇数处理掉，再处理奇数和偶数相邻的情况。

实现：

1 #include 
     
       2 using namespace std; 3  4 int gcd(int a, int b) 5 { 6     return !b ? a : gcd(b, a % b); 7 } 8  9 int n, a[100005];10 11 int main()12 {13     cin >> n;14     int g = 0;15     for (int i = 0; i < n; i++)16     {17         cin >> a[i];18         if (!i) g = a[i];19         else g = gcd(g, a[i]);20     }21     if (g > 1)22     {23         puts("YES\n0\n"); return 0;24     }25     int cnt = 0;26     for (int i = 0; i < n; i++)27     {28         if (!(a[i] & 1)) continue;29         else if (i + 1 < n)30         {31             if (a[i + 1] & 1) cnt++;32             else cnt += 2;33             i++;34         }35         else cnt += 2;36     }37     cout << "YES" << endl << cnt << endl;38     return 0;39 }
     

标程：

1 # include 
     
       2 using namespace std; 3 # define fi cin 4 # define fo cout 5 int main(void) 6 { 7     int n; 8     fi>>n; 9     int g = 0,v,cnt = 0,ans = 0;10     while (n --)11     {12         int v;13         fi>>v;14         g = __gcd(g,v);15         if (v & 1) ++cnt;16         else ans += (cnt / 2) + 2 * (cnt & 1),cnt = 0;17     }18     ans += (cnt / 2) + 2 * (cnt & 1);19     fo << "YES\n";20     if (g == 1)21         fo << ans << '\n';22     else23         fo << "0\n";24     cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';25     return 0;26 }