acwing1246. 等差数列

题目

题解

等差数列的公差肯定是每项的公约数，要使项数最少，那么只需要公差是每项的最大公约数即可。
若d=0,说明是每项都相等，直接输出n；

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int a[N];
int gcb(int a,int b){
    return b?gcb(b,a%b):a;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    int d=0;
    for(int i=1;i<n;i++)d=gcb(d,a[i]-a[0]);
    if(!d)cout<<n<<endl;
    else cout<<(a[n-1]-a[0])/d+1<<endl;
    
    return 0;
}