本文主要是介绍Mike and gcd problem(思维),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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.
Examples
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.
题意:给定一组序列,通过若干次变化是指成为一个美丽的序列。美丽序列的定义是,数组中所有数字的最大公因数大于1。问是否能转换成这样的一个序列,并且最少的变换次数是多少。
思路:一定可以转换成。
如果这个序列一开始就是最大公因数大于1,那么就不需要变换。如果不是的话,就有这样的几种情况。奇奇,偶偶,奇偶,偶奇。对于偶偶来说,不用管。对于其他三种情况来说
①奇奇:转换成偶偶,只需要一步。
②奇偶,偶奇:转换成偶偶需要两步。
因为求最少的步数,所以我们应该应该多转换奇奇,其次是奇偶,偶奇。
所以我们先找数组中的奇奇,然后再找奇偶,或者偶奇。
代码如下:
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxx=1e5+100;
int a[maxx];
int n;int main()
{scanf("%d",&n);scanf("%d",&a[1]);int cnt=a[1];for(int i=2;i<=n;i++) {scanf("%d",&a[i]);cnt=__gcd(cnt,a[i]);}ll sum=0;if(cnt>1) {cout<<"YES"<<endl<<sum<<endl;return 0;}for(int i=1;i<n;i++){if((a[i]&1)&&(a[i+1]&1)) sum++,a[i]+=1,a[i+1]+=1;}for(int i=1;i<n;i++){if((a[i]+a[i+1])&1) sum+=2,a[i]=a[i+1]=2;//都转换成偶数。。}cout<<"YES"<<endl<<sum<<endl;
}
努力加油a啊,(o)/~
这篇关于Mike and gcd problem(思维)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!