【题解】gcd游戏

题意

给一个长度为的数组，每次可以选择一个，让。问操作多少次，最终得到的数组。

题解

最简单的一个方法就是让数组总的，那只要让所有的数变为偶数即可。那么我们可以考虑相连两个数的不同情况。$

1. 和都为偶数，那么不需要进行操作。
2. 和都为奇数，对于操作来说就是两个奇数进行加减，两个奇数的加减得到的都是偶数，所以只需要操作一次就可以了。
3. 为奇数为偶数，奇数减偶数为奇数，偶数加奇数变为奇数。所以操作一次和都变为奇数，再操作一次可以都变为偶数。
4. 为偶数为奇数，由于要求操作次数最少，那么不与进行操作，优先与进行判断，若，那么只能进行两次变化变为偶数。

   复杂度

   时间复杂度

   代码

   #include<bits/stdc++.h>
   using namespace std;
   const int N=1e5+5;
   int a[N];
   int main()
   {
   int n;
   scanf("%d",&n);
   scanf("%d",&a[1]);
   int g = a[1];
   for(int i = 2;i <= n;i++)
   {
       scanf("%d",&a[i]);
       g = __gcd(g,a[i]);
   }
   if(g > 1)
   {
       printf("0\n");
       return 0;
   }
   int ans = 0;
   for(int i = 1;i < n;i++)
   {
       if(a[i]%2 && a[i+1]%2 == 0)
       {
           ans += 2;
       }
       else if(a[i]%2 && a[i+1]%2)
       {
           ans++;
           a[i+1]++;
       }
   }
   if(a[n]%2)  ans += 2;
   printf("%d",ans);
   return 0;
   }