【算法 | 数论 No.1】AcWing1246. 等差数列

落日映苍穹つ 2024-04-27 07:01 3阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[AcWing算法提高学习专栏][AcWing]】  
> 🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> 🍓希望我们一起努力、成长，共同进步。

**原题链接：[点击直接跳转到该题目][Link 3]**

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣算法分析
 *  3️⃣代码编写

## 1️⃣题目描述 ##

![在这里插入图片描述][4b2a521e6bdb4dcfaa216be32668d4de.png]  
![在这里插入图片描述][ac51800ad6db41fd87732e155c7dabbe.png]

## 2️⃣算法分析 ##

整个题目的思路是**先求出数组元素之间的最大公约数**，**然后计算最大等差子序列的长度**。

那什么时候这个最大等差子序列的长度是最大的呢？我们根据等差数列公式来看：**`an = a1 + (n - 1)d`**，即`n = (an - a1) / d + 1`：**当`an`最小（但是取的是数组中的最大值）、`a1`最大（但是取的是数组中的最小值），同时`d`最大（即每个元素与第一个元素之间的差值的最大公约数）。**

## 3️⃣代码编写 ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    const int N = 1e5 + 10;
    int arr[N];
    
    int gcd(int a,int b)
    {
        
        return b ? gcd(b,a % b) : a;
    }
    
    int main()
    {
        
        int n;
        cin >> n;
        for(int i = 0;i < n;i++) scanf("%d",&arr[i]);
        sort(arr,arr + n);
        
        int d = 0;
        for(int i = 1;i < n;i++) d = gcd(d,arr[i] - arr[0]);
        if(!d) printf("%d\n",n);
        else printf("%d\n",(arr[n - 1] - arr[0]) / d + 1);
        return 0;
    }

**最后就顺利通过啦！！！及时复习其中包含的一些小的算法哈，比如欧几里得算法~**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[AcWing]: https://blog.csdn.net/m0_74352571/category_12481646.html
[Link 3]: https://www.acwing.com/problem/content/1248/
[4b2a521e6bdb4dcfaa216be32668d4de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/2ae01b90410c4178901360a5b097430c.png
[ac51800ad6db41fd87732e155c7dabbe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/27aba95a73cd48e8854f325e8664c743.png