【推导】Codeforces Round #410 (Div. 2) C. Mike and gcd problem

如果一开始就满足题意，不用变换。

否则，如果对一对ai，ai+1用此变换，设新的gcd为d，则有（ai - ai+1）mod d = 0，（ai + ai+1）mod d = 0

变化一下就是2 ai mod d = 0

2 ai+1 mod d = 0

也就是说，用两次变换之后，gcd至少扩大2倍，于是，最优方案就是我们将所有的奇数都变成偶数。

只需要找出所有奇数段，答案就是sigma（[奇数段的长度/2]+(奇数段的长度 mod 2 ==1 ?)）。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

int n;

ll a[100010];

int main(){

//	freopen("c.in","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;++i){

		scanf("%I64d",&a[i]);

	}

	int GCD=(int)a[1];

	for(int i=2;i<=n;++i){

		GCD=__gcd(GCD,(int)a[i]);

	}

	if(GCD!=1){

		puts("YES\n0");

		return 0;

	}

	int cnt=0,sta;

	for(int i=1;i<=n;++i){

		if(a[i]%2ll==1 && (i==1 || a[i-1]%2ll==0)){

			sta=i;

		}

		if(a[i]%2ll==1 && (i==n || a[i+1]%2ll==0)){

			cnt+=(i-sta+1)/2+((i-sta+1)%2==1 ? 2 : 0);

		}

	}

	printf("YES\n%d\n",cnt);

	return 0;

}

巴特西

【推导】Codeforces Round #410 (Div. 2) C. Mike and gcd problem

最新文章

热门文章