【题解】gcd游戏
题意
给一个长度为的数组
,每次可以选择一个
,让
。问操作多少次,最终得到的
数组
。
题解
最简单的一个方法就是让数组总的,那只要让所有的数变为偶数即可。那么我们可以考虑相连两个数的不同情况。$
和
都为偶数,那么不需要进行操作。
和
都为奇数,对于操作来说就是两个奇数进行加减,两个奇数的加减得到的都是偶数,所以只需要操作一次就可以了。
为奇数
为偶数,奇数减偶数为奇数,偶数加奇数变为奇数。所以操作一次
和
都变为奇数,再操作一次可以都变为偶数。
为偶数
为奇数,由于要求操作次数最少,那么
不与
进行操作,优先
与
进行判断,若
,那么只能进行两次变化变为偶数。
复杂度
时间复杂度代码
#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; }