AcWing 1246. 等差数列最大公约数-白红宇的个人博客

发布日期：2021-05-12 17:10:48 浏览次数：16 分类：精选文章

本文共 315 字，大约阅读时间需要 1 分钟。

把这52个数从小到大排列，有序排列后是2，4，6，8，10，12，14，16，18，20个数字。然后我们来寻找所有相邻的差，比如： 2和4的差是2， 4和6的差是2， 6和8的差是2，以此类推，最大的公约数是2。于是公差d=2，整个数列是2,4,6,8,...,20。计算这个等差数列的长度，可以用（20-2）除以2再加上1，即18/2=9，加1等于10个。这样最短的等差数列就是10个数字。

我们来看代码实现：

首先对数组进行排序。

计算所有相邻数的差的最大公约数。

根据最大数与最小数，以及公差，计算最短等差数列的长度。

从中可以看出，算法的关键步骤就是计算数列的最小公差，然后根据最小值和最大值来计算最长可能的等差数列。

上一篇：AcWing 1295. X的因子链理解

下一篇：AcWing 1233. 全球变暖 bfs+判断

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章