第10回ブルーブリッジカップ等差数列正解

時間制限:1.0 sメモリ制限:256.0 MB本題総得点:20点
【問題の説明】
数学の先生は明ちゃんに等差数列の和を求める問題を出した.しかし不注意な明ちゃんは一部の数列を忘れ、その中のN個の整数しか覚えていない.今このN個の整数を与えて、明ちゃんはこのN個の整数を含む最も短い等差数列がいくつあることを知りたいですか?
【入力形式】
入力された最初の行には、整数Nが含まれます.2行目はN個の整数A 1,A 2,・・,A Nを含む.(注意A 1〜A Nは必ずしも等差数列の順に与えられるものではない)
【出力形式】
答えを表す整数を出力します.
【サンプル入力】
5 2 6 4 10 20
【サンプル出力】
10
【サンプル説明】
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 
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問題はそんなに簡単ではありません
正解:
問題に与えられた1段の数列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
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);
	else{
		printf("%d ",(a[N-1]-a[0])/d+1);
	}
	return 0;
	
}