题目链接：
题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
输入描述
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,··· ,AN。(注意 A1 ∼ AN 并不一定是按等差数列中的顺序给出)
编辑
输出描述
输出一个整数表示答案。
输入输出样例
示例
输入
5 2 6 4 10 20
输出
10
样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
JAVA解法：
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int arr[] = new int[num]; for (int i = 0; i < num; i++) { arr[i] = sc.nextInt(); } Arrays.sort(arr); int gcd = 0,min=arr[0],max = arr[num-1]; for (int i=2;i<num;i++){ gcd = gcd(gcd,arr[i]-arr[i-1]); } if (gcd == 0) System.out.println(num); else System.out.println((max-min)/gcd+1); } public static int gcd(int a,int b){ return b!=0?gcd(b,a%b):a; } }
C++解法：
#include <iostream> #include <algorithm> using namespace std; long long a[100001]; int y(int a,int b)//求最大公约数 { if(b==0)return a; else return y(b,a%b); } int main() { int n,i; 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=y(d,a[i]-a[i-1]); } if(a[n-1]==a[0])cout<<n<<endl;//考虑特殊情况 else cout<<((a[n-1]-a[0])/d)+1<<endl;//等差数列公式 return 0; }
python解法：
# 测试数据太弱了，直接算公差最大时的长度就行。。。 n = int(input()) lst = list(map(int,input().split())) lst.sort() d = 999 # d表示公差 for i in range(n-1): d = min(d, lst[i+1]-lst[i]) # 找能取到的最大公差 if d == 0: print(len(lst)) else: print(int((lst[-1] - lst[0])/d + 1))
