2018蓝桥模拟赛 蒜头君的数轴

脑子锈咯，看了题解才理出来。

这里提到的希望n-1个点的距离都一致，为了让加的点尽可能的小，这个距离其实就是这n-2个距离值的公共gcd的最大值。（公共的gcd,对应多个值的最大共同部分，）

这里处理完之后就是利用gcd的前后缀处理一下挖去一个点的之后的区间gcd

#include <iostream>  
#include <stdio.h>  
#include <algorithm>  
  
using namespace std;  
  
const int maxn = 1e5+10;  
int gcd1[maxn];   //gcd1[i]是前i个距离的gcd  
int gcd2[maxn];   //gcd2[i]是后i个距离的gcd  
int arr[maxn];  
long long dist[maxn];  
int gcd(int a,int b) {  
    if(b==0) return a;  
    else return gcd(b,a%b);  
}  
int main() {  
    int n;  
    long long sum;  
    while(~scanf("%d",&n)) {  
        for(int i = 0; i < n; i++) {  
            scanf("%d",&arr[i]);  
        }  
        if(n<=3) {  
            printf("0
");  
            continue;  
        }  
        sort(arr,arr+n);  
        sum = 0;  
        for(int i = 1; i < n; i++) {  
            dist[i] = arr[i]-arr[i-1];  
            sum += dist[i];  
        }  
        int d = dist[0];  
        for(int i = 1; i <= n-1; i++) {  
            d = gcd(d,dist[i]);  
            gcd1[i] = d;  
        }  
        d = dist[n-1];  
        for(int i = 1; i <= n-1; i++) {  
            d = gcd(d,dist[n-i]);  
            gcd2[i] = d;  
        }  
        int Min = 0x3f3f3f3f;  
        int temp;  
        //枚举删除每一个区间  
        for(int i = 1; i <= n-1; i++) {  
            if(i == 1) {  
                temp = (sum-dist[i])/gcd2[n-2];  
            }  
            else if(i == n-1) {  
                temp = (sum-dist[i])/gcd1[n-2];  
            }  
            else {  
                temp = (sum-dist[i])/gcd(gcd1[i-1],gcd2[n-1-i]);  
            }  
            Min = min(Min,temp-(n-2));  
        }  
        printf("%d
",Min);  
    }  
    return 0;  
}