Mike and gcd problem

题意翻译

# 问题描述 Mike给定一个$n$个元素的整数序列,$A=[a1,a2,...,an]$,每次操作可以选择一个 $i (1 \le i<n)$，将$a[i],a[i+1]$变成 $a[i]-a[i+1]$和$a[i]+a[i+1]$。现在想要的是$A$序列所有元素的最大公约数大于$1$ 1，请计算最少的操作次数。 # 输入数据 第一行一个整数 $n (2 \le n \le 100000)$ 第二行$n$个整数 $a1,a2,...,an (1 \le ai \le 10^9)$ # 输出 两行 第一行 一个字符串$YES$或$NO$表示能否使公约数大于1 第二行一个整数，表示最少的操作次数，如果无解输出 −1.

题目描述

Mike has a sequence $ A=[a_{1},a_{2},...,a_{n}] $ of length $ n $ . He considers the sequence $ B=[b_{1},b_{2},...,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&lt;n $ ), delete numbers $ a_{i},a_{i+1} $ and put numbers $ a_{i}-a_{i+1},a_{i}+a_{i+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 $ b_{i} $ for every $ i $ ( $ 1<=i<=n $ ).

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2<=n<=100000 $ ) — length of sequence $ A $ . The second line contains $ n $ space-separated integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — elements of sequence $ A $ .

输出格式

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.

输入输出样例

输入样例 #1

2
1 1

输出样例 #1

YES
1

输入样例 #2

3
6 2 4

输出样例 #2

YES
0

输入样例 #3

2
1 3

输出样例 #3

YES
1

说明

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 $ .

题意翻译

#### 题目描述 Mike 有一个长度为 $n$ 的序列 $A=[a_1,a_2,\dots,a_n]$。他认为一个序列 $B=[b_1,b_2,\dots,b_n]$ 是优美的，当且仅当其所有元素的 $\gcd$ 大于 $1$，即 $\gcd(b_1,b_2,\dots,b_n)>1$。 Mike 想要对他的序列进行操作来使它变为优美的。每次操作，他可以选择一个下标 $i(1\leqslant i<n)$，删除 $a_i$ 和 $a_{i+1}$，然后把 $a_i-a_{i+1}$ 和 $a_i+a_{i+1}$ 放回这两个位置上。他希望操作次数尽可能少。如果序列可以变为优美的，你需要给出最少操作次数，否则，指出不可能。 $\gcd(b_1,b_2,\dots,b_n)$ 是最大的非负整数 $d$ 使得 $d$ 整除每一个 $b_i(1\leqslant i\leqslant n)$。 #### 输入格式 第一行一个整数 $n(2\leqslant n\leqslant 10^5)$，表示序列 $A$ 的长度。 之后一行，$n$ 个被空格隔开的整数 $a_1,a_2,\dots,a_n(1\leqslant a_i\leqslant10^9)$，表示 $A$ 中的元素。 #### 输出格式 如果可以使序列变为优美的，第一行输出 `YES`，然后第二行输出最小操作次数。 如果不可能使得序列变为优美的，在第一行输出 `NO`。