Codeforces 798C：Mike and gcd problem

Codeforces 798C：Mike and gcd problem

题目链接：http://codeforces.com/contest/798/problem/C

题目大意：给出一个大小为$n$的数列，每次操作可以使得$a_i=a_i-a_{i+1}$，$a_{i+1}=a_i+a_{i+1}$，问最少多少次操作可以使得$gcd{a_i}>1$.

考虑$gcd(x,y)=1$的情况：若有$d eq 1$，$d|x-y$且$d|x+y$，则有$d|2x$且$d|2y$，故$d=2$，也就是说$gcd(x-y,x+y)=1$或$2$.

故若对于初始数列$gcd{a_i}=1$，那么多次操作后得到$gcd{a_i}=2$.

于是问题就转化为了，将数列中所有元素变成偶数所需要的最少操作数.

可以用dp解决（好像用贪心也是可以的）.

定义状态：

$dp[i][1]$为前$i-1$个数均为偶数，第$i$个数为奇数的最少操作数；
$dp[i][0]$为前$i-1$个数均为偶数，第$i$个数为偶数的最少操作数.

则有四种情况：

第$i$个数为偶数，第$i+1$个数为偶数时，将第$i+1$个数变成偶数不需要进行操作，而无法使第$i+1$个数变成奇数；
第$i$个数为偶数，第$i+1$个数为奇数时，将第$i+1$个数变成偶数需要进行$2$次操作，将第$i+1$个数变成奇数不需要进行操作；
第$i$个数为奇数，第$i+1$个数为偶数时，将第$i+1$个数变成偶数需要进行$2$次操作，而无法使第$i+1$个数变成奇数；
第$i$个数为奇数，第$i+1$个数为奇数时，将第$i+1$个数变成偶数需要进行$1$次操作，而无法使第$i+1$个数变成奇数；

复杂度为$O（nlg(Max{a_i})）$.

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string>
 5 #define N 100005
 6 using namespace std;
 7 typedef long long ll;
 8 int inf=10000000;
 9 int n,a[N],ans,dp[N][2];
10 bool p[N];
11 int gcd(int a,int b){
12     return b==0?a:gcd(b,a%b);
13 }
14 int main(void){
15     scanf("%d",&n);
16     for(int i=0;i<n;++i){
17         scanf("%d",&a[i]);
18         p[i]=a[i]%2;
19     }
20     ans=a[0];
21     for(int i=0;i<n;++i)ans=gcd(ans,a[i]);
22     if(ans==1){
23         dp[0][!p[0]]=inf;
24         for(int i=1;i<n;++i){
25             if(p[i]){
26                 dp[i][0]=min(dp[i-1][0]+2,dp[i-1][1]+1);
27                 dp[i][1]=min(dp[i-1][0],inf);
28             }else{
29                 dp[i][0]=min(dp[i-1][0],dp[i-1][1]+2);
30                 dp[i][1]=min(inf,inf);
31             }
32         }
33         if(dp[n-1][0]!=inf)printf("YES
%d",dp[n-1][0]);
34         else printf("NO");
35     }else printf("YES
0");
36 }