第十届蓝桥杯省赛C/C++B组 试题H 等差数列

【解题思路】将N个整数进行排序，最后全部的数一定在第一个元素和最后一个元素之间，依次求前后两个数的差（显然这应该是公差的倍数），最后求出这些差的最大公因数就是公差了，利用等差数列公式就能知道全部的项的数。

#include <stdio.h>
#include <math.h>
int gcd(int a,int b);
int gcd(int a,int b){      //欧几里得算法求最大公约数 
	int t;
	if(a<b){
		t=a;a=b;b=t;
	}
	int num;
	while(b!=0){
		num=a%b;
		a=b;
		b=num;
	}
	return a;
}
int main() {
    int n;
    int d[100000];
    int i,j,t;
    scanf("%d",&n);
    for(i=0;i<n;i++){
    	scanf("%d",&d[i]);
	}
	for(i=0;i<n-1;i++){      //对数组进行排序 
		for(j=0;j<n-i-1;j++){
			if(d[i]>d[i+1]){
				t=d[i];d[i]=d[i+1];d[i+1]=t;
			}
		}
	}
	int cha[100000];
	for(i=0;i<n-1;i++){      //求差值 
		cha[i]=d[i+1]-d[i];
	}
	int gcds;
	for(i=0;i<n-2;i++){      //求出所有差值的最大公约数 
		gcds=gcd(cha[i],cha[i+1]);
	}

	int ans;
	ans=((d[n-1]-d[0])/gcds)+1;      //将数组最大值-最小值,除最大公约数再+1,即可算出个数 
	printf("%d",ans);
	return 0;
}

网上找的大佬C++算法：

#include<stdio.h>
#include<stdlib.h>
int arr[100001];
int d[100001];

int gcd(int a, int b){
	return b==0?a:gcd(b,a%b);
}

int* cmp(const int *a,const int *b){
	return *(int*)a - *(int*)b;
}

int main(){
	int n,i,j,d_;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&arr[i]);
	}
	qsort(arr,n,sizeof(int),cmp);

	j=0;
	for(i=0;i<n-1;i++){
		d[j++] = arr[i+1]-arr[i];
	}
	d_ = gcd(d[0],d[1]);
	for(i=2;i<j;i++){
		d_ = gcd(d_,d[i]);
	}
	printf("%d\n",(arr[n-1]-arr[0])/d_ + 1);
	return 0;
}