2305: 蓝桥杯2019年第十届省赛真题-等差数列

每相邻的两项的差的最大公约数 == d

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[100005];
long long b[100005];
long gcd(long x,long y)
{
    if(y > x){
    	int t = x;
    	x = y;
    	y = t;
	}
	while(x % y != 0){
		int z = x % y;
		x = y;
		y = z;
	}
	return y;
}
int main(){
	cin>>n;
	for(int i = 0; i < n; i++){
		cin>>a[i];
	}
	sort(a, a + n);
	if(a[1] - a[0] == 0){//当公差为0时
		cout<<n;
		return 0;
	}
	long y = gcd(a[1] - a[0], a[2] - a[1]);
	for(int i = 3; i < n; i++){
		y = gcd(y, a[i] - a[i - 1]);
	}
	cout<<(a[n - 1] - a[0]) / y + 1; 
	return 0;
}