[蓝桥杯][2019年第十届真题]等差数列

思路

要求包含这 N 个整数的最短的等差数列有几项，则首项取数组(A)中的最小值，末项取数组(A)中的最大值。

假设公差为(d)，首相为(A[0])，则相邻两项的差(A[i]-A[0]，i in [1,n-1])一定是公差(d)的倍数，于是对所有相邻两项的差求(gcd)即可得到公差(d)。

const int N=1e5+10;
int a[N];
int n;

int gcd(int a,int b)
{
    return b?gcd(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=gcd(d,a[i]-a[i-1]);

    if(d == 0) cout<<n<<endl;
    else cout<<(a[n-1]-a[0])/d+1<<endl;
    //system("pause");
    return 0;
}