【计蒜客 A1633 — 程序设计：蒜头君的数轴】gcd私忆一秒钟的博客-

题目来源：点击进入【计蒜客 A1633 — 程序设计：蒜头君的数轴】

Description

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

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

Input

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

第二行为 n 个不重复的整数 x1,x2,…,xn (−109≤xi≤109)，表示这些点的坐标，点坐标乱序排列。

Output

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

Sample Input

4
1 3 7 15

Sample Output

1

解题思路：

首先我们分析题意：所谓的优美实际上是除了一对点之外，使其他相邻点距离相同。
那么既然是相同，而且要使加入的点最少，所以我们需要考虑除了某一对以外其他点之间距离的最大公约数，这样只需要在公约数处加入点即可。
当然我们还要排除那唯一一对的情况。所以我们可以通过两个数组分别记录从左到i和从右到i的最大公约数，通过最大公约数，我们可以得到左右两边最后一共有多少点，减去原本就有的点即需要加入的点。然后遍历这个i,使左右两边需要加入的点最少。

AC代码(C++)：

#include <iostream> #include <algorithm> #define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define endl 'n' using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const int MAXN = 1e5+5; int arr[MAXN],l[MAXN],r[MAXN]; int gcd(int a, int b) { if (a<b) swap(a,b); return (a%b == 0) ? b : gcd(b,a%b); } int main() {     SIS; int n,ans=inf;     cin >> n; for(int i=0;i<n;i++) cin >> arr[i]; sort(arr,arr+n); int sum=arr[n-1]-arr[0];     l[1]=arr[1]-arr[0];     r[n-2]=arr[n-1]-arr[n-2]; for(int i=2;i<n;i++)         l[i]=gcd(l[i-1],arr[i]-arr[i-1]); for(int i=n-3;i>=0;i--)         r[i]=gcd(r[i+1],arr[i+1]-arr[i]);     ans=min(ans,(sum-arr[1]+arr[0])/r[1]-n+2);     ans=min(ans,(sum-arr[n-1]+arr[n-2])/l[n-2]-n+2); for(int i=1;i<n-2;i++)         ans=min(ans,(sum-arr[i+1]+arr[i])/gcd(l[i],r[i+1])-n+2);     cout << ans << endl; return 0; }