等差数列

题目 等差数列

思路分析

缺省的等差数列 给的数全要在这个等差数列里面

反正已知的数都是成等差的性质的 后一项减前一项等于公差d

每一项与第一项的差一定是d的倍数

长度怎么算 末项减首项除以公差+1 \((a*n-a*1)/d+1\)

首项可以确定 用当前数中给的最小值 末项也可以确定 用当前数中给的最大值

那么唯一不确定是就是这个d了

要让这个公式结果最小 那就是要让d最大

又每一项减第一项都是d的倍数

所以可以转变为 求这些d的一个最大公约数 gcd

另外考虑d为0的情况 长度就是给的所有数

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int a[N];

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

int main()
{
    int n;cin>>n;
    int first=0x3f3f3f,last=-0x3f3f3f;
    for(int i=0;i<n;i++){
        cin>>a[i];
        first=min(first,a[i]);
        last=max(last,a[i]);
    }
    int max_d=0;
    for(int i=1;i<n;i++)
        max_d=__gcd(max_d,a[i]-first);
              //gcd(max_d,a[i]-first);

    if(!max_d)
        cout<<n<<endl;
    else
        cout<<(last-first)/max_d+1<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 欧几里得算法（辗转相除） 🏠 00-刷题理模型 ➡️ 约数个数