D. Arpa and a list of numbers

Codeforces

IDCF851D

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Arpa has found a list containing _n_ numbers. He calls a list bad if and only if it is not empty and _gcd_ (see notes section for more information) of numbers in the list is 1. Arpa can perform two types of operations: * Choose a number and delete it with cost _x_. * Choose a number and increase it by 1 with cost _y_. Arpa can apply these operations to as many numbers as he wishes, and he is allowed to apply the second operation arbitrarily many times on the same number. Help Arpa to find the minimum possible cost to make the list good. ## Input First line contains three integers _n_, _x_ and _y_ (1 ≤ _n_ ≤ 5·105, 1 ≤ _x_, _y_ ≤ 109) — the number of elements in the list and the integers _x_ and _y_. Second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the elements of the list. ## Output Print a single integer: the minimum possible cost to make the list good. [samples] ## Note In example, number 1 must be deleted (with cost 23) and number 16 must increased by 1 (with cost 17). A _gcd_ (greatest common divisor) of a set of numbers is the maximum integer that divides all integers in the set. Read more about gcd [here](https://en.wikipedia.org/wiki/Greatest_common_divisor).

Arpa 找到了一个包含 $n$ 个数字的列表。他称一个列表为“坏的”，当且仅当它非空且列表中数字的 _gcd_（详见注释部分）为 $1$。 Arpa 可以执行两种操作： Arpa 可以对任意多个数字应用这些操作，并且他允许对同一个数字无限次应用第二种操作。帮助 Arpa 找到使列表变“好”的最小可能代价。第一行包含三个整数 $n$、$x$ 和 $y$（$1 ≤ n ≤ 5·10^5$，$1 ≤ x, y ≤ 10^9$）— 列表中元素的个数以及整数 $x$ 和 $y$。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^6$）— 列表的元素。请输出一个整数：使列表变“好”的最小可能代价。在示例中，数字 $1$ 必须被删除（代价为 $23$），数字 $16$ 必须增加 $1$（代价为 $17$）。一组数的 _gcd_（最大公约数）是能整除集合中所有整数的最大整数。有关 gcd 的更多信息，请参见此处。 ## Input 第一行包含三个整数 $n$、$x$ 和 $y$（$1 ≤ n ≤ 5·10^5$，$1 ≤ x, y ≤ 10^9$）— 列表中元素的个数以及整数 $x$ 和 $y$。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^6$）— 列表的元素。 ## Output 请输出一个整数：使列表变“好”的最小可能代价。 [samples] ## Note 在示例中，数字 $1$ 必须被删除（代价为 $23$），数字 $16$ 必须增加 $1$（代价为 $17$）。一组数的 _gcd_（最大公约数）是能整除集合中所有整数的最大整数。有关 gcd 的更多信息，请参见此处。

**Definitions:** - Let $ n, x, y \in \mathbb{Z}^+ $, with $ 1 \leq n \leq 5 \cdot 10^5 $, $ 1 \leq x, y \leq 10^9 $. - Let $ A = [a_1, a_2, \dots, a_n] $, where $ a_i \in \mathbb{Z}^+ $, $ 1 \leq a_i \leq 10^6 $. **Operations:** 1. **Delete** any element $ a_i $ at cost $ x $. 2. **Increment** any element $ a_i $ by 1 any number of times; each increment costs $ y $. (Thus, increasing $ a_i $ to $ a_i + k $ costs $ k \cdot y $.) **Goal:** Transform $ A $ into a list $ A' $ (possibly empty) such that: - $ A' $ is **not bad**, i.e., either: - $ A' = \emptyset $, or - $ \gcd(A') > 1 $. Minimize the total cost of operations to achieve this. **Objective:** $$ \min_{A'} \left( x \cdot (\text{number of deletions}) + y \cdot \left( \sum_{a_i \in A'} (a_i' - a_i) \right) \right) $$ subject to: - $ A' $ is obtained from $ A $ by deleting some elements and incrementing others (non-negative integer increments), - $ A' = \emptyset $ or $ \gcd(A') > 1 $. **Note:** Incrementing is only allowed upward; no decrements.

Samples

Input #1

4 23 17
1 17 17 16

Output #1

Input #2

10 6 2
100 49 71 73 66 96 8 60 41 63

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Arpa and a list of numbers",
    "description": {
      "content": "Arpa has found a list containing _n_ numbers. He calls a list bad if and only if it is not empty and _gcd_ (see notes section for more information) of numbers in the list is 1. Arpa can perform two t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF851D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arpa has found a list containing _n_ numbers. He calls a list bad if and only if it is not empty and _gcd_ (see notes section for more information) of numbers in the list is 1.\n\nArpa can perform two t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Arpa 找到了一个包含 $n$ 个数字的列表。他称一个列表为“坏的”，当且仅当它非空且列表中数字的 _gcd_（详见注释部分）为 $1$。\n\nArpa 可以执行两种操作：\n\nArpa 可以对任意多个数字应用这些操作，并且他允许对同一个数字无限次应用第二种操作。\n\n帮助 Arpa 找到使列表变“好”的最小可能代价。\n\n第一行包含三个整数 $n$、$x$ 和 $y$（$1 ≤ n ≤ 5·10^5$...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n\n- Let $ n, x, y \\in \\mathbb{Z}^+ $, with $ 1 \\leq n \\leq 5 \\cdot 10^5 $, $ 1 \\leq x, y \\leq 10^9 $.\n- Let $ A = [a_1, a_2, \\dots, a_n] $, where $ a_i \\in \\mathbb{Z}^+ $, $ 1 \\leq a_i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments