本题核心公式:
最小项数 = (最小项-最大项)/最大公差 + 1
最大公差直接用gcd(欧几里得算法)从头到尾扫一遍得出所有与第一项的差值的最大公约数
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100010
using namespace std;
int a[N],n;
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
int main()
{
scanf("%d",&n);
for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
sort(a,a+n);
int d = 0;
//找出d的最大公约数
for(int i = 1;i < n;i ++) d = gcd(d,a[i]-a[0]);
if(!d) printf("%d\n" , n);
else printf("%d\n" , (a[n-1] - a[0]) / d + 1);
}