嗯...

 

题目链接：https://www.luogu.org/problemnew/show/CF798C

 

这道题首先要会写gcd..也类似一种找规律吧...

 

问题的操作是在两个数的基础上进行的：

那么我们不妨只考虑两个数的操作，手写几组数据不难发现，所有写出来的两个数A.B，都会在至多两次操作内完成任务。那么我们可以考虑其性质：

 

两个数A.B.无非四种情况：

奇数，奇数--------------->操作后变成       偶数，偶数

奇数，偶数--------------->操作后变成       奇数，奇数

偶数，奇数--------------->操作后变成       奇数，奇数

偶数，偶数--------------->操作后变成       偶数，偶数

 

所以：

如果原来两个数都是偶数的话，那么操作数为0.

如果原来两个数都是奇数的话，那么操作数为1.

如果原来两个数是一奇一偶的话，那么操作数为2.

其一定不会出现结果是（3 ，6）这种情况的，除非原序列就是这样的。

 

所以，最后再加几个特判即可：

如果n == 1，其gcd一定是1，所以直接输出即可；

如果gcd在不操作之前已经大于1了，直接输出即可；

其他情况再讨论奇偶性即可...（注意这道题不存在无解的情况，前面已经解释过）....

 

AC代码：

1 #include
      
        2 #include
       
         3  4 using namespace std; 5  6 int n, a[100005], ans; 7  8 int gcd(int a, int b){ 9     if(b == 0)10         return a;11     return gcd(b, a % b);12 }13 14 int main(){15     scanf("%d", &n);16     for(int i = 1; i <= n; i++)17         scanf("%d", &a[i]);18     if(n == 1){19         printf("YES\n0\n");20         return 0;21     }//特判 22     int now = gcd(a[1], a[2]);23     for(int i = 3; i <= n; i++)24         now = gcd(a[i], now);//gcd 25     if(now != 1){26         printf("YES\n0\n");27         return 0;28     }//特判 29     else{30         a[n + 1] = 0;31         for(int i = 1; i <= n; i++){32             if(a[i] % 2 == 1 && a[i + 1] % 2 == 1){33                 ans++;34                 a[i + 1] = 0;//已经操作成偶数，所以赋值成任何一个偶数都可 35             }36             else if(a[i] % 2 == 1 && a[i + 1] % 2 == 0)//一奇一偶 37                 ans += 2;38         }39         printf("YES\n%d\n", ans);40     }41     return 0;42 }