题解 CF798C 【Mike and gcd problem】

· · 题解

偶然间看到这么好的题目

发现居然没有一篇题解。。。

所以我来安利一篇别人的题解

原帖 https://blog.csdn.net/mengxiang000000/article/details/71155450

题目大意：

我们有一种操作，选择两个相邻的数（Ai，Ai+1）能够将其变成：（Ai-Ai+1，Ai+Ai+1）；

我们希望最终的数组的|Gcd（A1,A2,A3,A4,A5..............）|>1.询问最少需要操作多少步。

思路：

问题的操作是在两个数的基础上进行的。

那么我们不妨只考虑两个数的操作，手写几组数据不难发现，所有写出来的两个数A.B，都会在至多两次操作内完成任务。那么我们可以考虑其性质：

两个数A.B.无非四种情况： 奇数，奇数--------------->操作后变成       偶数，偶数

奇数，偶数--------------->操作后变成       奇数，奇数

偶数，奇数--------------->操作后变成       奇数，奇数

偶数，偶数--------------->操作后变成       偶数，偶数

所以：

如果原来两个数都是偶数的话，那么操作数为0.

如果原来两个数都是奇数的话，那么操作数为1.

如果原来两个数是一奇一偶的话，那么操作数为2.

而后我们考虑结果，其最终可行解为两种情况：

①偶数 偶数的话，那么没有什么异议.

②奇数 奇数的话，只有这两个数相等且>1的话才会满足结果。

其一定不会出现结果是（3 ，6）这种情况的，除非原序列就是这样的。

那么我们不妨将问题推展到三个数，如果结果是（奇数 奇数 奇数）的话，我们肯定原来序列和结果序列是一样的，而且这三个奇数是相等且大于1的。

否则不可能有这样的结果，反之，如果结果是（偶数 偶数 偶数）的话，那么是没有异议的。

所以如果原序列的结果是>1的，那么操作数需要为0.

反之我们将原序列全部变成偶数即可。

Ac代码：

#include<bits/stdc++.h>
using namespace std;
int a[1555555],n,i,j,gc,ans,t;
int gcd(int x,int y)
{
    if(y==0)
    {
        return x;
    }
    else
    {
        return gcd(y,x%y);
    }
}
int main()
{
    cin>>n;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<n;i++)
    {
        gc=gcd(gc,a[i]);
    }
    if(gc>1)
    {
        cout<<0;
    }
    else
    {
        for(i=0;i<n-1;i++)
        {
            while(abs(a[i])%2==1)
            {
                ans++;
                t=a[i];
                a[i]=a[i]-a[i+1];
                a[i+1]=t+a[i+1];
            }
        }
        while(abs(a[n-1])%2==1)
        {
            ans++;
            t=a[n-2];
            a[n-2]=a[n-2]-a[n-1];
            a[n-1]=t+a[n-1];
        }
        if(ans)
        {
            cout<<ans;
        }
        else
        {
            cout<<-1;
        }
    }
    return 0;
}