P8795 [蓝桥杯 2022 国 A] 选素数

server/2024/12/29 1:42:26/

题目描述:

小蓝有一个数 x,每次操作小蓝会选择一个小于 x 的素数 p,然后在 x 成为 p 的倍数前不断将 x 加 1,(如果 x 一开始就是 p 的倍数则 x 不变)。

小乔看到了小蓝进行了 2 次上述操作后得到的结果 n,他想知道 x 在一开始是多少。如果有多种可能,他想知道 x 一开始最小可以是多少,而如果不存在任何解,说明小乔看错了,此时请输出 −1。

输入格式

输入一行包含一个整数 n,表示经过两次操作后 x 的值。

输出格式

输出一行包含一个整数表示 x 的初始值。如果有多个解,输出最小的。如果不存在解,请输出 −1。

输入输出样例

输入 #1

22

输出 #1

8

说明/提示

【评测用例规模与约定】

  • 对于 60% 的评测用例,1≤n≤5000;
  • 对于所有评测用例,1≤n≤1e6。

蓝桥杯 2022 国赛 A 组 G 题。

解题思路:

我们先将题目简化一下,假设只求一次操作数后最小值。先拆解一下题目。首先这个输入数n是某个质数的k倍,那么这个初始数一定是在这个质数的k倍和(k-1)倍之间,因为若小于质数的(k-1)倍,在初始数不断++的过程中就会提前终止。同时题目又要求这个数为最小值,那么这个数就是输入数n的最大质因数+1。(我们暂且将其定义为x)

同理可得,我们通过第一次的计算算出了x,那么第二次的要找的操作数就在x和n之间,我们只需要依次算出他们的最大质因数,然后通过(操作数-最大质因数+1)的方法求得最小初始值。

举个例子如果说输入的数是39,那么它的最大质因数就是13,将39-13+1后得到27,那么第二次的操作数就在27,28,30,32,33,34,35,36,38之间产生。通过上面的方法我们一次对这些数进行运算,如法炮制,算出他们的最小初始值,然后进行比较得到整个数组的最小初始值,就能获得最终的最小操作数。上述的结果得到34的最大质因数17,34-17+1得到18,那么18就是初始值。

下面我们进行代码书写。

样例代码:

#include<iostream>
using namespace std;const int MAXN = 1000001;
int m, t;                    // m:输入数值,t:质数计数
bool isprime[MAXN];
int prime[MAXN];             // p存储质数
int p[MAXN];                 // 存储某个数最大的质因数
int ans = 1e9;               // 用来存储最小的符合条件的值// f函数用于计算给定的数字m的值,返回结果为 (m - p[m] + 1)
int f(int m)
{if (isprime[m] == true)   // 如果m是质数{return 1e9;           // 返回一个非常大的值}return (m - p[m] + 1);     // 返回 (m 减去最大质因数 p[m] + 1)
}// 线性筛法(欧拉筛法)
// 用于筛出 1 到 m 之间的所有质数
void Linear_sieve()
{for (int i = 2; i <= m; i++)   // 从 2 开始遍历到 m{isprime[i] = true;         // 假设每个数都是质数}for (int i = 2; i <= m; i++)   // 遍历每个数字{if (isprime[i])            // 如果当前数是质数{t++;                   // 质数计数器加 1prime[t] = p[i] = i;   // prime[t] 存储当前质数 i,p[i] 存储 i}// 从当前质数 i 开始遍历后续数for (int j = 1; j <= t && i * prime[j] <= m; j++){p[i * prime[j]] = max(p[i], prime[j]);  // 更新 i * prime[j] 的最大质因数isprime[i * prime[j]] = false;           // 将 i * prime[j] 标记为合数if (i % prime[j] == 0)  // 为了避免重复计算,减少多余的操作{break;  // 如果 i 已经能被 prime[j] 整除,跳出循环,避免重复标记}}}
}int main()
{cin >> m;Linear_sieve();      // 通过线性筛法生成质数和更新其他数组// 下面的循环是为了找出最小的符合条件的数for (int i = f(m); i <= m; i++) // 循环从 f(m) 到 m{ans = min(ans, f(i));   // 计算 f(i),并更新 ans 为最小值}// 如果 ans 被更新过,说明找到了符合条件的结果if (ans != 1e9){cout << ans << endl;  // 输出最小的符合条件的值}else{cout << "-1" << endl;  // 没有找到符合条件的值,输出 -1}return 0;
}

代码解读:

我们首先遍历2到m的数,将它们假设为质数(true),那么后序我们只需要排除掉不是质数的数(false)。Linear_sieve()是欧拉筛法,用于筛选出质数,并且将每个数的最大质因数保存在p数组中。


http://www.ppmy.cn/server/152952.html

相关文章

公交车信息管理系统:实现交通数据的智能化处理

概述 在对系统进行设计之前&#xff0c;需要对选题进行需求分析、可行性分析、流程分析、数据字典等内容。根据需求分析阶段&#xff0c;大致确定用户使用系统所需要具有的功能模块需求&#xff0c;由此规划出系统需要设计的相关功能模块。根据可行性分析阶段&#xff0c;确定系…

计算机网络•自顶向下方法:计算机网络和因特网

因特网的具体构成 终端&#xff08;host&#xff09;也称端系统&#xff08;end system&#xff09;&#xff1a;运行应用程序 通信链路&#xff1a;光纤&#xff0c;铜线&#xff0c;电磁波&#xff0c; 主要指标为传输速率&#xff0c;也称带宽(bandwidth) 交换设备&#x…

前端开发 之 12个鼠标交互特效上【附完整源码】

前端开发 之 12个鼠标交互特效上【附完整源码】 文章目录 前端开发 之 12个鼠标交互特效上【附完整源码】一&#xff1a;彩色空心爱心滑动特效1.效果展示2.HTML完整代码 二&#xff1a;彩色实心爱心滑动特效1.效果展示2.HTML完整代码 三&#xff1a;粒子连结特效1.效果展示2.HT…

精准提升:从94.5%到99.4%——目标检测调优全纪录

&#x1f680; 目标检测模型调优过程记录 在进行目标检测模型的训练过程中&#xff0c;我们面对了许多挑战与迭代。从初始模型的训练结果到最终的调优优化&#xff0c;每一步的实验和调整都有其独特的思路和收获。本文记录了我在优化目标检测模型的过程中进行的几次尝试&#…

如何在Windows系统上安装和配置Node.js及Node版本管理器(nvm)

Node.js是一个基于Chrome V8引擎的JavaScript运行时环境&#xff0c;广泛用于开发高性能的网络应用。它使得JavaScript不仅能在浏览器端运行&#xff0c;还能在服务器端执行。对于开发者来说&#xff0c;Node.js是现代Web应用的核心之一。安装和配置Node.js后&#xff0c;很多开…

Blazor 直接读取并显示HTML 文件内容

如果你想在 Blazor 中直接读取 并显示HTML 文件&#xff0c;可以使用 .NET 的文件读取方法&#xff0c;比如 File.ReadAllText。Blazor Server&#xff08;服务端&#xff09;可以通过服务器的文件系统访问文件。 以下是针对 Blazor Server 的解决方案&#xff1a; 1. 使用 Fi…

鸿蒙学习记录之http网络请求

权限申请 路径为&#xff1a;entry -> src -> main -> module.json5 "requestPermissions": [{"name": "ohos.permission.INTERNET",}] 基本使用 // 1. 引入包名 import { http } from kit.NetworkKit;// 2. 创建一个HttpRequest对…

C++设计模式:享元模式 (附文字处理系统中的字符对象案例)

什么是享元模式&#xff1f; 享元模式是一个非常实用的结构型设计模式&#xff0c;它的主要目的是节省内存&#xff0c;尤其在需要创建大量相似对象时。 通俗解释&#xff1a; 想象我们在写一本书&#xff0c;每个字母都需要表示出来。如果每个字母都单独用对象表示&#xff…