蓝桥杯:等差数列
发布日期:2021-06-28 15:43:54 浏览次数:2 分类:技术文章

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

蓝桥杯:等差数列

题解:

此题为明显的gcd(最大公约数)问题。

首先明白我们想要组成的等差数列最短,那么在我们对给定的几个整数排好序后,最大和最小的的一定是边界项。
既然边界已经固定,我们只需要确定公差即可。
又因为想要数列长度尽可能的短,因此我们尽量去选择最大的公差。
而公差与什么有关呢?
我们可以得知其与每两个数之间的间隔有关,即最大公差即为每两个数之间的间隔的gcd。
在求最大公约数时我们可以先找定其理想上的最大公约数,即几个整数中最小的那个。(因为公约数不能大于数本身)
然后看其是否满足要求,即是否能被整除,不满足则减小直到找到即可。

代码:

#include
#include
using namespace std;int a[100000];int cmp(const void*x,const void*y){
int a = *(int*)x; int b = *(int*)y; return a>b?1:-1;} int main() {
int n; int d; scanf("%d",&n); for(int i=0;i

转载地址:https://blog.csdn.net/xiangguang_fight/article/details/115706408 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:蓝桥杯:后缀表达式
下一篇:蓝桥杯:质数

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年04月25日 20时03分17秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章