首页 > 代码库 > CodeForce-798C Mike and gcd problem（贪心）

CodeForce-798C Mike and gcd problem（贪心）

2024-09-19 04:48:46   206人阅读

Mike has a sequence A?=?[a1,?a2,?...,?an] of length n. He considers the sequence B?=?[b1,?b2,?...,?bn] beautiful if the gcd of all its elements is bigger than 1, i.e. 技术分享.

Mike wants to change his sequence in order to make it beautiful. In one move he can choose an index i (1?≤?i?<?n), delete numbers ai,?ai?+?1 and put numbers ai?-?ai?+?1,?ai?+?ai?+?1 in their place instead, in this order. He wants perform as few operations as possible. Find the minimal number of operations to make sequence A beautiful if it‘s possible, or tell him that it is impossible to do so.

技术分享 is the biggest non-negative number d such that d divides bi for every i (1?≤?i?≤?n).

Input

The first line contains a single integer n (2?≤?n?≤?100?000) — length of sequence A.

The second line contains n space-separated integers a1,?a2,?...,?an (1?≤?ai?≤?109) — elements of sequence A.

Output

Output on the first line "YES" (without quotes) if it is possible to make sequence A beautiful by performing operations described above, and "NO" (without quotes) otherwise.

If the answer was "YES", output the minimal number of moves needed to make sequence A beautiful.

Example
Input
2
1 1
Output
YES
1
Input
3
6 2 4
Output
YES
0
Input
2
1 3
Output
YES
1
Note

In the first example you can simply make one move to obtain sequence [0,?2] with 技术分享.

In the second example the gcd of the sequence is already greater than 1.

题意:n个数,n<=1e5,操作:把a[i],a[i+1] 替换成 a[i]-a[i+1],a[i]+a[i+1],问至少要多少次操作才能让整个a数组的最大公约数gcd大于1.

由题目给出操作可知：当gcd(a,b)<=1时，进行操作为：

初始：a  b

第一步：a-b  a+b

第二步：-2b  2a

即两个数最多2步操作就能满足GCD==2。

对于两个偶数，要进行0步操作；对于两个奇数，要进行1步操作；对于一个奇数一个偶数，要进行2步操作。

先把所有“2个奇数成对”的情况计数+1并把两个奇数更新为偶数，然后在重新判断所有“1个奇数1个偶数成对”的情况计数+2。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200050],n,num=0;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    ll ans=gcd(abs(a[1]),abs(a[2]));
    for(int i=3;i<=n;i++)        ans=gcd(ans,abs(a[i]));
    if(ans>1) cout<<"YES"<<endl<<0<<endl;  
    else
    {
        for(int i=1;i<n;i++)
        if(a[i]%2&&a[i+1]%2)
            a[i]=0,a[i+1]=0,num++;
        for(int i=1;i<n;i++)
        if((a[i]%2&&a[i+1]%2==0)||(a[i]%2==0&&a[i]%2))
            a[i]=0,a[i+1]=0,num+=2;
        cout<<"YES"<<endl<<num<<endl;
    } 
    return 0;
}

 

CodeForce-798C Mike and gcd problem（贪心）


联系
我们