原题链接：/contest/798/problem/C
题意：有一个数列A，gcd(a1,a2,a3...,an)>1 时称这个数列是“漂亮”的。存在这样的操作，使ai,ai+1变为(ai-ai+1), (ai+ai+1)。问最少进行这样的操作使数列是“漂亮”的。
思路：考虑gcd(a1,a2,a3...,an)>1 的情况：
我们对ai,ai+1进行两次操作可以得到2ai,2ai+1，也就是说一对相邻的数字最多操作2次使它们的gcd=2>1。而对于一对奇数来说，操作一次就能使它们成为偶数。
现在就是要把数列中所有的数变为偶数。先对相邻奇数进行操作（每次+1），再对单个奇数进行操作（每次+2）即可。
AC代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int MAXN=2e6+5; 6 long long num[MAXN]; 7 long long gcd(long long a, long long b){ 8return (b==0)?a:gcd(b, a%b); 9 }10 int main()11 {12int n;13while(cin>>n){14 memset(num, 0, sizeof(num));15 for(int i=0;i<n;i++){16 cin>>num[i];17 }18 long long g=gcd(num[0], num[1]); 19 for(int i=2;i<n;i++){20 g=gcd(g, num[i]);21 if(g==1)22 break;23 }24 if(g>1){25 cout<<"YES"<<endl;26 cout<<0<<endl;27 continue;28 }29 int res=0;30 for(int i=1;i<n;i++){31 if(num[i-1]%2&&num[i]%2){32 num[i-1]++;33 num[i]++;34 res++;35 }36 }37 for(int i=1;i<n;i++){38 if(num[i-1]%2&&num[i]%2==0||(num[i]%2&&num[i-1]%2==0)) {39 num[i-1]=0;40 num[i]=0;41 res+=2;42 }43 }44 cout<<"YES"<<endl;45 cout<<res<<endl;46}4748return 0;49 }
