题目来源：点击进入【计蒜客 A1633 — 程序设计：蒜头君的数轴】 Description 今天蒜头君拿到了一个数轴，上边有 n 个点，但是蒜头君嫌这根数轴不够优美，想要通过加一些点让它变优美，所谓优美是指考虑相邻两个点的距离，最多只有一对点的距离与其它的不同。 蒜头君想知道，他最少需要加多少个点使这个数轴变优美。 Input 输入第一行为一个整数 n(1≤n≤105)，表示数轴上的点数。 第二行为 n 个不重复的整数 x1,x2,…,xn (−109≤xi≤109)，表示这些点的坐标，点坐标乱序排列。 Output 输出一行，为一个整数，表示蒜头君最少需要加多少个点使这个数轴变优美。 Sample Input 4 Sample Output 1 解题思路： 首先我们分析题意：所谓的优美实际上是除了一对点之外，使其他相邻点距离相同。 AC代码(C++)：
【计蒜客 A1633 — 程序设计：蒜头君的数轴】gcd
1 3 7 15
那么既然是相同，而且要使加入的点最少，所以我们需要考虑除了某一对以外其他点之间距离的最大公约数，这样只需要在公约数处加入点即可。
当然我们还要排除那唯一一对的情况。所以我们可以通过两个数组分别记录从左到i和从右到i的最大公约数，通过最大公约数，我们可以得到左右两边最后一共有多少点，减去原本就有的点即需要加入的点。然后遍历这个i,使左右两边需要加入的点最少。#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; }
