今天蒜头君拿到了一个数轴，上边有 nn 个点，但是蒜头君嫌这根数轴不够优美，想要通过加一些点让它变优美，所谓优美是指考虑相邻两个点的距离，最多只有一对点的距离与其它的不同。

蒜头君想知道，他最少需要加多少个点使这个数轴变优美。

输入格式

输入第一行为一个整数 n(1 \leq n \leq 10^5)n(1≤n≤105)，表示数轴上的点数。

第二行为 nn 个不重复的整数 x_1,x_2,...,x_n(-10^9 \leq x_i \leq 10^9)x1​,x2​,...,xn​(−109≤xi​≤109)，表示这些点的坐标，点坐标乱序排列。

输出格式

输出一行，为一个整数，表示蒜头君最少需要加多少个点使这个数轴变优美。

样例输入<button class="jsk&#45;btn&#45;link jsk&#45;fr jsk&#45;text&#45;sm" data&#45;clipboard&#45;target="&#35;id00523056204683960002" data&#45;jsk&#45;popover="&#123;content&#58; &#39;复制成功&#39;&#44; theme&#58; &#39;success sm&#39;&#125;" id="id0028975848959006090001">复制</button>

4
1 3 7 15

样例输出<button class="jsk&#45;btn&#45;link jsk&#45;fr jsk&#45;text&#45;sm" data&#45;clipboard&#45;target="&#35;id0057054133123102570004" data&#45;jsk&#45;popover="&#123;content&#58; &#39;复制成功&#39;&#44; theme&#58; &#39;success sm&#39;&#125;" id="id0051846853431313970003">复制</button>

1

 

思路：

如果不考虑可以有一个区间不同，让我们求的是所有的区间都要优美。至少需要多少个点？

很简单，我们就去求所有区间长度的gcd  求得的gcd就是最小区间长度

考虑最多只有一对点的距离与其他的不同，即此时我们可以去除一个间隔求出 gcd，那么现在我们要去除哪一个间隔才能使得加点的个数最小呢？

假设某相邻两点之间的距离为 x ，此时我们加点的目标间隔为 gcd，那么显然我们需要在这两点之间增加 x/gcd−1个点。

综上得出结论，我们期望的 gcd 越大越好，因为这样加点的个数会越小。

pos[i]代表去除第 i 个间隔以后的 gcdgcd ，显然它可以通过前缀 gcd 与后缀 gcd 配合求出。

随后我们找出 pos 中的最大值，设为 maxx ，则 maxx 为解的最优间隔，枚举所有相邻两点的距离，求解需要加点的个数。

可能会出现两种情况：

一、某个区间长度不可以分成符合gcd的倍数的形式。那其实就说明我们去除的就是这个区间。 比如 1，4，4，8 ，8     它的maxx = gcd(4,4,8,8) = 4   那么第一个区间长度1 肯定被去除了

二、所有区间都可以分成符合gcd的倍数的形式。那么我们就去除需要分成份数最多的。 比如4，4，4，8，8   它的maxx  = gcd(4,4,4,8,8) = 4  所有区间都可以分成4的倍数，那么我们就去除分成份数最多的区间 8

 

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdlib.h>
 4 #include <string>
 5 #include <string.h>
 6 #include <set>
 7 #include <queue>
 8 #include <stdbool.h>
 9 
10 #define LL long long
11 using namespace std;
12 const int MAXN=100005;
13 
14 int leftt[MAXN],rightt[MAXN],pos[MAXN];
15 int a[MAXN],b[MAXN];
16 int n;
17 
18 int gcd(int a,int b)
19 {
20     int t;
21     while (b)
22     {
23         t = b;
24         b = a%b;
25         a = t;
26     }
27     return a;
28 }
29 
30 int main()
31 {
32 #ifndef ONLINE_JUDGE
33     freopen("../in.txt","r",stdin);
34 #endif
35     scanf("%d",&n);
36     for (int i=0;i<n;i++)
37         scanf("%d",&a[i]);
38     sort(a,a+n);
39     for (int i=1;i<n;i++)
40         b[i] = a[i]-a[i-1];
41     leftt[1] = b[1];
42     for (int i=2;i<n;i++)
43     {
44         leftt[i] = gcd(leftt[i-1],b[i]);
45     }
46     rightt[n-1] = b[n-1];
47     for (int i=n-2;i>0;i--)
48     {
49         rightt[i] = gcd(b[i],rightt[i+1]);
50     }
51     pos[1] = rightt[2];
52     pos[n-1] = leftt[n-2];
53     for (int i=2;i<n-1;i++)
54         pos[i] = gcd(leftt[i-1],rightt[i+1]);
55     int maxx = pos[1];
56     for (int i=2;i<n;i++)
57     {
58         if (pos[i]>maxx)
59             maxx = pos[i];
60     }
61     int ans = 0,ms = 0,cnt = 0;
62     for (int i=1;i<n;i++)
63     {
64         if (b[i]%maxx != 0)
65         {
66             cnt++;
67             continue;
68         }
69         ans += b[i]/maxx - 1;
70         ms = max(ms,b[i]/maxx-1);
71     }
72     if (!cnt)
73         ans -= ms;
74     cout << ans << endl;
75     return 0;
76 }