首页 > 代码库 > 798C - Mike and gcd problem

798C - Mike and gcd problem

题意


通过将一组序列中 ai与ai+1 变为 ai-ai+1 与ai+ai+1 的操作将这组序列的gcd变成不为1。

 



看了题解才会写== ,所以叫做补提嘛QWQ,当
d|a && d|b 时 d|ax+by ,即 d|ai-ai+1 d|ai+ai+1 时,可得 d|2ai, d|2ai+1

从而新序列的gcd一定为2,所以先求出所有数字的gcd(因为我太菜的原因不知道算gcd的复杂度其实不高,log(max(a,b))这样,如果不等于1,直接输出0。

然后再贪心扫两遍就行。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_NUM   1000003
int num[MAX_NUM];
int dp[MAX_NUM][2];
int exchang[MAX_NUM];
int gcd(int a, int b){
    if( b == 0 )
        return a;
    return gcd(b,a%b);
}
int main(int argc, char const *argv[])
{
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i)
        scanf("%d",&num[i]);
    int pre = gcd(num[1],num[2]);
    for (int i = 3; i <= n ; ++i)
        pre =  gcd(pre,num[i]);
    if(pre!=1){
        printf("YES\n");
        printf("0\n");
        return 0;
    }
    int ans = 0;
    for (int i = 2; i <= n; ++i)
    {
        if(num[i-1]&1&&num[i]&1){
            ans++;
            num[i-1] = 0;
            num[i] = 0;
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        if(num[i-1]&1||num[i]&1){
            ans+=2;
            num[i-1] = 0;
            num[i] = 0;
        }
    }
    printf("YES\n%d\n",ans );
    return 0;
}

 

798C - Mike and gcd problem