B. Add Points

Codeforces

IDCF953B

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

There are _n_ points on a straight line, and the _i_\-th point among them is located at _x__i_. All these coordinates are distinct. Determine the number _m_ — the smallest number of points you should add on the line to make the distances between all neighboring points equal. ## Input The first line contains a single integer _n_ (3 ≤ _n_ ≤ 100 000) — the number of points. The second line contains a sequence of integers _x_1, _x_2, ..., _x__n_ ( - 109 ≤ _x__i_ ≤ 109) — the coordinates of the points. All these coordinates are distinct. The points can be given in an arbitrary order. ## Output Print a single integer _m_ — the smallest number of points you should add on the line to make the distances between all neighboring points equal. [samples] ## Note In the first example you can add one point with coordinate 0. In the second example the distances between all neighboring points are already equal, so you shouldn't add anything.

在一条直线上有 #cf_span[n] 个点，其中第 #cf_span[i] 个点位于 #cf_span[xi] 处。所有这些坐标互不相同。求出最小的点数 #cf_span[m] —— 你需要在直线上添加的最少点数，使得所有相邻点之间的距离相等。第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 100 000]) —— 点的数量。第二行包含一个整数序列 #cf_span[x1, x2, ..., xn] (#cf_span[ - 109 ≤ xi ≤ 109]) —— 点的坐标。所有坐标互不相同，点的给出顺序任意。请输出一个整数 #cf_span[m] —— 为使所有相邻点之间的距离相等，你需要在直线上添加的最少点数。在第一个例子中，你可以添加一个坐标为 #cf_span[0] 的点。在第二个例子中，所有相邻点之间的距离已经相等，因此无需添加任何点。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 100 000]) —— 点的数量。第二行包含一个整数序列 #cf_span[x1, x2, ..., xn] (#cf_span[ - 109 ≤ xi ≤ 109]) —— 点的坐标。所有坐标互不相同，点的给出顺序任意。 ## Output 请输出一个整数 #cf_span[m] —— 为使所有相邻点之间的距离相等，你需要在直线上添加的最少点数。 [samples] ## Note 在第一个例子中，你可以添加一个坐标为 #cf_span[0] 的点。在第二个例子中，所有相邻点之间的距离已经相等，因此无需添加任何点。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of given points. Let $ X = \{x_1, x_2, \dots, x_n\} \subset \mathbb{R} $ be the set of distinct coordinates of the points. **Constraints** 1. $ 3 \leq n \leq 100{,}000 $ 2. $ -10^9 \leq x_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 3. All $ x_i $ are distinct. **Objective** Sort $ X $ into an ordered sequence $ x_{(1)} < x_{(2)} < \dots < x_{(n)} $. Let $ d_i = x_{(i+1)} - x_{(i)} $ for $ i = 1, \dots, n-1 $ be the gaps between consecutive points. Let $ g = \gcd(d_1, d_2, \dots, d_{n-1}) $ be the greatest common divisor of all gaps. Compute the minimal number of points to add: $$ m = \sum_{i=1}^{n-1} \left( \frac{d_i}{g} - 1 \right) $$

Samples

Input #1

3
-5 10 5

Output #1

Input #2

6
100 200 400 300 600 500

Output #2

Input #3

4
10 9 0 -1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Add Points",
    "description": {
      "content": "There are _n_ points on a straight line, and the _i_\\-th point among them is located at _x__i_. All these coordinates are distinct. Determine the number _m_ — the smallest number of points you should",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF953B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ points on a straight line, and the _i_\\-th point among them is located at _x__i_. All these coordinates are distinct.\n\nDetermine the number _m_ — the smallest number of points you should...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在一条直线上有 #cf_span[n] 个点，其中第 #cf_span[i] 个点位于 #cf_span[xi] 处。所有这些坐标互不相同。\n\n求出最小的点数 #cf_span[m] —— 你需要在直线上添加的最少点数，使得所有相邻点之间的距离相等。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 100 000]) —— 点的数量。\n\n第二行包含一个整数序列 #...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of given points.  \nLet $ X = \\{x_1, x_2, \\dots, x_n\\} \\subset \\mathbb{R} $ be the set of distinct coordinates of the points.  \n\n**Constraints**...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments