C. Mike and gcd problem

Codeforces

IDCF798C

Time2000ms

Memory256MB

Difficulty—

dpgreedynumber theory

English · Original

Chinese · Translation

Formal · Original

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_ < _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_). ## 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_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 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. [samples] ## 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.

Mike 有一个长度为 $n$ 的序列 $A = [a_1, a_2, ..., a_n]$。他定义序列 $B = [b_1, b_2, ..., b_n]$ 是美丽的，当且仅当它的所有元素的 $\gcd$ 大于 $1$，即 $\gcd(b_1, b_2, ..., b_n) > 1$。 Mike 希望通过操作将他的序列变为美丽的。在一次操作中，他可以选择一个索引 $i$（$1 \leq i < n$），删除数字 $a_i, a_{i+1}$，并用 $a_i - a_{i+1}, a_i + a_{i+1}$ 替换它们，按此顺序放置。他希望尽可能少地执行操作。请找出使序列 $A$ 变得美丽的最少操作次数，如果不可能则告诉他无法做到。其中 $\gcd$ 是最大的非负整数 $d$，使得 $d$ 能整除每个 $b_i$（$1 \leq i \leq n$）。第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$）——序列 $A$ 的长度。第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^9$）——序列 $A$ 的元素。如果可以通过上述操作使序列 $A$ 变得美丽，则在第一行输出 "_YES_"（不含引号），否则输出 "_NO_"（不含引号）。如果答案是 "_YES_"，则输出使序列 $A$ 变得美丽的最少操作次数。在第一个例子中，你只需执行一次操作即可得到序列 $[0, 2]$，其 $\gcd$ 为 $2$。在第二个例子中，序列的 $\gcd$ 已经大于 $1$。 ## Input 第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$）——序列 $A$ 的长度。第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^9$）——序列 $A$ 的元素。 ## Output 如果可以通过上述操作使序列 $A$ 变得美丽，则在第一行输出 "_YES_"（不含引号），否则输出 "_NO_"（不含引号）。如果答案是 "_YES_"，则输出使序列 $A$ 变得美丽的最少操作次数。 [samples] ## Note 在第一个例子中，你只需执行一次操作即可得到序列 $[0, 2]$，其 $\gcd$ 为 $2$。在第二个例子中，序列的 $\gcd$ 已经大于 $1$。

**Definitions** Let $ n \in \mathbb{Z} $, $ n \geq 2 $, be the length of sequence $ A = (a_1, a_2, \dots, a_n) $, where $ a_i \in \mathbb{Z} $ and $ 1 \leq a_i \leq 10^9 $. A sequence $ B = (b_1, b_2, \dots, b_n) $ is *beautiful* if $ \gcd(b_1, b_2, \dots, b_n) > 1 $. An operation consists of choosing an index $ i \in \{1, 2, \dots, n-1\} $, deleting $ (a_i, a_{i+1}) $, and replacing them with $ (a_i - a_{i+1}, a_i + a_{i+1}) $, in that order. **Constraints** 1. $ 2 \leq n \leq 100{,}000 $ 2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Determine the minimal number of operations required to transform $ A $ into a beautiful sequence, or determine that it is impossible. Let $ G = \gcd(a_1, a_2, \dots, a_n) $. If $ G > 1 $, then no operations are needed. Otherwise, find the minimum number of operations such that the resulting sequence has $ \gcd > 1 $. If impossible, output "NO".

Samples

Input #1

2
1 1

Output #1

YES
1

Input #2

3
6 2 4

Output #2

YES
0

Input #3

2
1 3

Output #3

YES
1

API Response (JSON)

{
  "problem": {
    "name": "C. Mike and gcd problem",
    "description": {
      "content": "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. . Mi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF798C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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. .\n\nMi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mike 有一个长度为 $n$ 的序列 $A = [a_1, a_2, ..., a_n]$。他定义序列 $B = [b_1, b_2, ..., b_n]$ 是美丽的，当且仅当它的所有元素的 $\\gcd$ 大于 $1$，即 $\\gcd(b_1, b_2, ..., b_n) > 1$。\n\nMike 希望通过操作将他的序列变为美丽的。在一次操作中，他可以选择一个索引 $i$（$1 \\leq i <...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the length of sequence $ A = (a_1, a_2, \\dots, a_n) $, where $ a_i \\in \\mathbb{Z} $ and $ 1 \\leq a_i \\leq 10^9 $.  \nA sequence $ B = (b_1, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments