{"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 add on the line to make the distances between all neighboring points equal.\n\n## Input\n\nThe first line contains a single integer _n_ (3 ≤ _n_ ≤ 100 000) — the number of points.\n\nThe 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.\n\n## Output\n\nPrint a single integer _m_ — the smallest number of points you should add on the line to make the distances between all neighboring points equal.\n\n[samples]\n\n## Note\n\nIn the first example you can add one point with coordinate 0.\n\nIn the second example the distances between all neighboring points are already equal, so you shouldn't add anything.","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第二行包含一个整数序列 #cf_span[x1, x2, ..., xn] (#cf_span[ - 109 ≤ xi ≤ 109]) —— 点的坐标。所有坐标互不相同，点的给出顺序任意。\n\n请输出一个整数 #cf_span[m] —— 为使所有相邻点之间的距离相等，你需要在直线上添加的最少点数。\n\n在第一个例子中，你可以添加一个坐标为 #cf_span[0] 的点。\n\n在第二个例子中，所有相邻点之间的距离已经相等，因此无需添加任何点。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 100 000]) —— 点的数量。第二行包含一个整数序列 #cf_span[x1, x2, ..., xn] (#cf_span[ - 109 ≤ xi ≤ 109]) —— 点的坐标。所有坐标互不相同，点的给出顺序任意。\n\n## Output\n\n请输出一个整数 #cf_span[m] —— 为使所有相邻点之间的距离相等，你需要在直线上添加的最少点数。 \n\n[samples]\n\n## Note\n\n在第一个例子中，你可以添加一个坐标为 #cf_span[0] 的点。在第二个例子中，所有相邻点之间的距离已经相等，因此无需添加任何点。","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**  \n1. $ 3 \\leq n \\leq 100{,}000 $  \n2. $ -10^9 \\leq x_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. All $ x_i $ are distinct.  \n\n**Objective**  \nSort $ X $ into an ordered sequence $ x_{(1)} < x_{(2)} < \\dots < x_{(n)} $.  \nLet $ d_i = x_{(i+1)} - x_{(i)} $ for $ i = 1, \\dots, n-1 $ be the gaps between consecutive points.  \nLet $ g = \\gcd(d_1, d_2, \\dots, d_{n-1}) $ be the greatest common divisor of all gaps.  \n\nCompute the minimal number of points to add:  \n$$\nm = \\sum_{i=1}^{n-1} \\left( \\frac{d_i}{g} - 1 \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF953B","tags":[],"sample_group":[["3\n-5 10 5","1"],["6\n100 200 400 300 600 500","0"],["4\n10 9 0 -1","8"]],"created_at":"2026-03-03 11:00:39"}}