現在給出這N 個整數,小明想知道包含這N 個整數的最短的等差數列有幾項?
輸入的第壹行包含壹個整數N。
第二行包含N 個整數A1.A2,..., AN。(註意A1<=AN 並不壹定是按等差數列中的順序給出)
2<=N<=100000,0<=Ai<=10^9
輸出壹個整數表示答案。
5
2 6 4 10 20
10
包含2、6、4、10、20 的最短的等差數列是2、4、6、8、10、12、14、16、18、20。
題目可以理解為:對於N個數,最少補多少個數可以使這些數成為等差數列,即項數要最小。
對於升序排列的N個數,首項(a1)和尾項(an)壹定是固定的。因為沒有必要在第壹個數前或最後壹個數後再補充數列元素。
項數 = (an-a1) / d + 1
公差d越大,項數越小
有如下兩個結論(兩者用壹個即可):
公差d壹定可以整除數列中每壹個數ai減第壹個數a1,即:(ai-a1)%d = 0,則公差d最大為(ai-a1)的最大公因數
公差d壹定可以整除數列中每壹個數ai減最後壹個數an,即:(an-ai)%d = 0,則公差d最大為(an-ai)的最大公因數
註意:需要特判公差全為0的情況