P8682 [蓝桥杯 2019 省 B] 等差数列

#include"bits/stdc++.h"

using namespace std;
/*
思路还是很简单的，即求出所有的公差d[i]=a[i]-a[i-1] ，然后找到
所有公差里相等的公差记为d[j]，然后求出d[j]的最大公约数即可 
到这里可以发现时间复杂度相当之大，而且相当繁琐。
所以我们不是全求出d[i]之后再求d[j]的最大公约数，而是一个接一个的求解、更新即可 
*/ 
int gcd(int x,int y)
{
	if(y==0)
	return x;
	return gcd(y,x%y);
}//求最大公约数 
int main()
{
	int n;
	cin >> n;
	int a[100050];
	for(int i=0;i<n;i++)
	cin >> a[i];
	sort(a,a+n);
	int ans=a[1]-a[0];
		if(a[n-1]==a[0])//判断是否为常数列 
		{
			cout <<n <<endl;
			return 0;
		}
			for(int i=2;i<n;i++)
			{
				ans=gcd(ans,a[i]-a[i-1]);//求解、更新最大公约数 
			} 
	cout << (a[n-1]-a[0])/ans+1;//项数 
	return 0;
 }