G - Mike and gcd problem

Mike has a sequence?A?=?[a₁,?a₂,?...,?a_n]?of length?n. He considers the sequence?B?=?[b₁,?b₂,?...,?b_n]?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?a_i,?a_i?+?1?and put numbers?a_i?-?a_i?+?1,?a_i?+?a_i?+?1in 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?b_i?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?a₁,?a₂,?...,?a_n?(1?≤?a_i?≤?10⁹) — elements of sequence?A.

Output

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

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

Example

Input 2
1 1 Output YES
1 Input 3
6 2 4 Output YES
0 Input 2
1 3 Output YES
1
題意：輸入n個數?(2?≤?n?≤?100?000），操作:把a[i],a[i+1] 替換成 a[i]-a[i+1],a[i]+a[i+1]，問最少多少次操作
使所有元素的gcd>1。 題解：假設兩個數a,b。操作一次a-b,a+b. 操作兩次 -2b，2a。gcd=2；
所以任意兩個數兩次操作后gcd一定>1；
當兩個數是偶數時，需要0次操作
當兩個是奇數時，需要1次操作
當一奇一偶時，需要2次操作
先循環一遍兩個都是奇數的，然后把這兩個數更改為偶數，操作次數+1；
在循環一遍一奇一偶成對的，然后把這兩個數更改為偶數，操作次數+2； 代碼： #include<iostream> #include<string> #include<algorithm> #include<cstring> #include<cstdlib> #include<cstdio> long long gcd(long long a,long long b) {if(b==0)return a;elsegcd(b,a%b); } using namespace std; int main() {long long a[100005],ans;int n,i,num=0;cin>>n;for(i=1;i<=n;i++)cin>>a[i];ans=gcd(a[1],a[2]);for(i=3;i<=n;i++)ans=gcd(ans,a[i]);if(ans>1)cout<<"YES"<<endl<<0<<endl;else{for(i=1;i<n;i++){if(a[i]%2&&a[i+1]%2){a[i]=0; a[i+1]=0; num++;}}for(i=1;i<n;i++){if(a[i]%2==0&&a[i+1]%2==1){a[i]=0; a[i+1]=0; num+=2;}else if(a[i]%2==1&&a[i+1]%2==0){a[i]=0; a[i+1]=0; num+=2;}elsecontinue;}cout<<"YES"<<endl<<num<<endl;} }

?

?

轉載于:https://www.cnblogs.com/GXXX/p/6814992.html

總結

以上是生活随笔為你收集整理的G - Mike and gcd problem的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。