{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"The 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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input\n\n3\n-5 10 5\n\nOutput\n\n1\n\nInput\n\n6\n100 200 400 300 600 500\n\nOutput\n\n0\n\nInput\n\n4\n10 9 0 -1\n\nOutput\n\n8"},{"iden":"note","content":"In 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."}],"translated_statement":[{"iden":"statement","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在第二个例子中，所有相邻点之间的距离已经相等，因此无需添加任何点。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 100 000]) —— 点的数量。第二行包含一个整数序列 #cf_span[x1, x2, ..., xn] (#cf_span[ - 109 ≤ xi ≤ 109]) —— 点的坐标。所有坐标互不相同，点的给出顺序任意。"},{"iden":"output","content":"请输出一个整数 #cf_span[m] —— 为使所有相邻点之间的距离相等，你需要在直线上添加的最少点数。 "},{"iden":"examples","content":"输入\n3\n-5 10 5\n输出\n1\n\n输入\n6\n100 200 400 300 600 500\n输出\n0\n\n输入\n4\n10 9 0 -1\n输出\n8"},{"iden":"note","content":"在第一个例子中，你可以添加一个坐标为 #cf_span[0] 的点。在第二个例子中，所有相邻点之间的距离已经相等，因此无需添加任何点。"}],"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":null,"has_page_source":false}