IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 蓝桥真题:等差数列(数论) -> 正文阅读

[数据结构与算法]蓝桥真题:等差数列(数论)

正文

题目描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中 N 个整数。
  现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有几项?

输入格式
  输入的第一行包含一个整数 N。
  第二行包含 N 个整数 A?, A?, · · · , AN。(注意 A? ~ AN 并不一定是按等差数列中的顺序给出)
输出格式
  输出一个整数表示答案。
样例输入
5
2 6 4 10 20
样例输出
10
样例说明
  包含 2641020 的最短的等差数列是 2468101214161820

题目思路及代码

思路:给你n个数,是某个等差数列的一部分,问该等差数列最小有几项?:( ( 最 大 数 ? 最 小 数 ) / d ) + 1 ,其中d是该等差数列所有(所有已知数与最小数差值)的最大公因数,还要特别考虑如果d = 0的时候,就是n
代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e6+10;
ll n;
ll a[maxn];
ll d[maxn];
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	ll ans=a[2]-a[1];
    if(ans==0){
        cout<<n;
        return 0;
    }
    for(int i=3;i<=n;i++){
        ans=gcd((ll)(a[i]-a[i-1]),ans);
    }
    ll cnt=(a[n]-a[1])/ans+1;
    cout<<cnt;
	return 0;
}

结语


“遇事不决可问春风,春风不语即随本心”的意思是:对一件事犹豫不决,就问春风该如何做,春风给不出答案,就凭自己本心做出决断。“遇事不决可问春风,春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》,其原文是:“遇事不决,可问春风。春风不语,遵循己心”。

在这里插入图片描述


  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-07 22:56:50  更:2022-04-07 22:57:07 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 9:58:40-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码