题目描述:
小蓝有一个数 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数组中。