時間限制: 1.0s 記憶體限制: 256.0MB 本題總分：20 分

【問題描述】

數學老師給小明出了一道等差數列求和的題目。但是粗心的小明忘記了一部分的數列，只記得其中 N 個整數。
現在給出這 N 個整數，小明想知道包含這 N 個整數的最短的等差數列有幾項？

【輸入格式】

輸入的第一行包含一個整數 N。
第二行包含 N 個整數 A 1 ,A 2 ,··· ,A N 。(注意 A 1 ∼ A N 並不一定是按等差數列中的順序給出)

【輸出格式】

輸出一個整數表示答案。

【樣例輸入】

5
2 6 4 10 20

【樣例輸出】

【樣例說明】

包含 2、6、4、10、20 的最短的等差數列是 2、4、6、8、10、12、14、16、18、20。

【評測用例規模與約定】
對於所有評測用例，2 ≤ N ≤ 100000，0 ≤ A i ≤ 109 10^910 9。

之所以寫這一篇題解，因爲看到網上千篇一律的題解都走進了一個誤區，就是「兩兩差值最小值就是公差」

然後就有了下面下麪的程式碼

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;cin>>n;
    int a[n+10];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int x = 99999999999;
    for(int i=1;i<n;i++){
        x = min(a[i]-a[i-1],x);
    }
    if(x==0) cout<<n<<endl;
    else {
        int ans = (a[n-1]-a[0])/x+1;
        cout<<ans<<endl;
    }
    return 0;
}

因爲這個我也鬱悶了很久，實在想不出來這程式碼的原理是什麼，這程式碼竟然還AC了！！！
假設給一個數列 1 3 8 那麼公差就是2嗎？顯然不是

藍橋杯的H題不會這麼簡單

正解：

要明白對於題目給的一段數列
2 6 4 10 20
首先對數列進行排序：2,4,6,10,20（這個應該毋庸置疑）
要使數列最短可以確定a[0]=2,a[n]=20;
由等差數列通項：an=a1+(n-1)*d →n=(an-a1)/d+1
這個時候我們只需要找出公差d的值就可以了
下面下麪一段話需要細品！！！
d={所有相鄰整數差的最大公約數}
有序數列所有整數差必定是公差的倍數纔可構成等差數列，也就是對於有序數列(a[n]-a[n-1])/d==0都要成立才行,要使數列最短，則公差儘可能大，所以只需要求所有差值的最大公約數即可

#include<bits/stdc++.h>
using namespace std;
int N,a[100005];
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	sort(a,a+N);
	//求差值最大公約數 
	int d=a[1]-a[0];
	for(int i=2;i<N;i++){
		 d=gcd(d,a[i]-a[i-1]);
	}
	if(d==0)printf("%d\n",N);
	else{
		printf("%d ",(a[N-1]-a[0])/d+1);
	}
	return 0;
	
}

第十屆藍橋杯 等差數列正解