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

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

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

#include
#include
int gcd(int a,int b);
int gcd(int a,int b){ //欧几里得算法求最大公约数
int t;
if(a 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 scanf("%d",&d[i]);
}
for(i=0;i for(j=0;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 cha[i]=d[i+1]-d[i];
}
int gcds;
for(i=0;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
#include
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 scanf("%d",&arr[i]);
}
qsort(arr,n,sizeof(int),cmp);
j=0;
for(i=0;i d[j++] = arr[i+1]-arr[i];
}
d_ = gcd(d[0],d[1]);
for(i=2;i d_ = gcd(d_,d[i]);
}
printf("%d\n",(arr[n-1]-arr[0])/d_ + 1);
return 0;
}