---
title: "等差数列"
created: 2025-11-28
tags:
  - 算法
---

# 等差数列

## 题目 [等差数列](https://www.acwing.com/problem/content/1248/)

![[image-a7bad39b.png]]

## 思路分析

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

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

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

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

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

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

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

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

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

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

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[约数个数|约数个数]]